Difference between revisions of "Automatentheorie"

From Glottopedia
Jump to navigation Jump to search
(New page: == Ursprung == *''griech. automatos'' - sich von selbst bewegend == Definition == Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Au...)
 
Line 1: Line 1:
== Ursprung ==
+
Die '''Automatentheorie''' befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme.
*''griech. automatos'' - sich von selbst bewegend
+
 
 +
===Kommentare===
  
== Definition ==
+
Die Automatentheorie befasst sich weniger mit der internen Struktur als mit dem Verhalten solcher Systeme; dies wird wiederum darauf reduziert, welche Folgen von Eingaben in das System welche Ausgaben erzeugen können. Bei unendlichen (wachsenden) Automaten spielt jedoch auch die Art und Weise des Wachstums eine wichtige Rolle. Bei Automaten mit potentiell unendlichem Speicher ist die Art des Speicherzugriffs und die Folge der Speicherinhalte wichtig.  
Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von [[Automaten]], d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme. Die Automatentheorie befasst sich weniger mit der internen Struktur als mit dem Verhalten solcher Systeme; dies wird wiederum darauf reduziert, welche Folgen von Eingaben in das System welche Ausgaben erzeugen können. Bei unendlichen (wachsenden) Automaten spielt jedoch auch die Art und Weise des Wachstums eine wichtige Rolle. Bei Automaten mit potentiell unendlichem Speicher ist die Art des Speicherzugriffs und die Folge der Speicherinhalte wichtig.  
 
 
Oft werden akzeptierende Automaten ([[Akzeptor]]) betrachtet, bei denen nur ihre akzeptierte Wortmenge interessiert, d.h. die Menge endlicher Eingabefolgen (Wörter), die den Automat von einem (oder mehreren) Anfangszuständen in einen von (im allgemeinen) mehreren Endzuständen überführen; die Ausgabe besteht also jeweils nur aus einem ''Ja'' oder ''Nein'' nach Ende der Eingabe. Symmetrisch dazu werden auch erzeugende Automaten ([[Generator]]) betrachtet.  
 
Oft werden akzeptierende Automaten ([[Akzeptor]]) betrachtet, bei denen nur ihre akzeptierte Wortmenge interessiert, d.h. die Menge endlicher Eingabefolgen (Wörter), die den Automat von einem (oder mehreren) Anfangszuständen in einen von (im allgemeinen) mehreren Endzuständen überführen; die Ausgabe besteht also jeweils nur aus einem ''Ja'' oder ''Nein'' nach Ende der Eingabe. Symmetrisch dazu werden auch erzeugende Automaten ([[Generator]]) betrachtet.  
 
Ferner behandelt man nicht nur [[deterministisch]] arbeitende Automaten (bei denen die Änderung des jeweiligen Zustands und die jeweilige Ausgabe funktional nur von der momentanen Eingabe und dem aktuellen Zustand abhängt), sondern auch [[Nicht-Determinismus|nicht-deterministische Automaten]], bei denen Relationen anstelle von Funktionen die mögliche Arbeitsweise beschreiben.  
 
Ferner behandelt man nicht nur [[deterministisch]] arbeitende Automaten (bei denen die Änderung des jeweiligen Zustands und die jeweilige Ausgabe funktional nur von der momentanen Eingabe und dem aktuellen Zustand abhängt), sondern auch [[Nicht-Determinismus|nicht-deterministische Automaten]], bei denen Relationen anstelle von Funktionen die mögliche Arbeitsweise beschreiben.  
Line 13: Line 13:
 
* Akzeptoren mit linear beschränktem Speicher ([[Linear Beschränkte Automaten]]) entsprechen [[kontextsensitive Sprachen|kontextsensitiven Sprachen]];
 
* Akzeptoren mit linear beschränktem Speicher ([[Linear Beschränkte Automaten]]) entsprechen [[kontextsensitive Sprachen|kontextsensitiven Sprachen]];
 
* [[Turing-Maschine|Turing-Maschinen]] charakterisieren die allgemeinsten mit endlichen Mitteln erzeugbaren formalen Sprachen, die aufzählbaren (oder Typ-0-)Sprachen.
 
* [[Turing-Maschine|Turing-Maschinen]] charakterisieren die allgemeinsten mit endlichen Mitteln erzeugbaren formalen Sprachen, die aufzählbaren (oder Typ-0-)Sprachen.
 +
 +
=== Ursprung ===
 +
*''griech. automatos'' - sich von selbst bewegend
  
 
{{wb}}
 
{{wb}}
 
[[Category:Computerlinguistik]]
 
[[Category:Computerlinguistik]]

Revision as of 15:19, 24 July 2008

Die Automatentheorie befasst sich mit der formalen mathematischen Beschreibung und Untersuchung von Automaten, d.h. von Modellen diskreter sequentieller informationsverarbeitender Systeme.

Kommentare

Die Automatentheorie befasst sich weniger mit der internen Struktur als mit dem Verhalten solcher Systeme; dies wird wiederum darauf reduziert, welche Folgen von Eingaben in das System welche Ausgaben erzeugen können. Bei unendlichen (wachsenden) Automaten spielt jedoch auch die Art und Weise des Wachstums eine wichtige Rolle. Bei Automaten mit potentiell unendlichem Speicher ist die Art des Speicherzugriffs und die Folge der Speicherinhalte wichtig. Oft werden akzeptierende Automaten (Akzeptor) betrachtet, bei denen nur ihre akzeptierte Wortmenge interessiert, d.h. die Menge endlicher Eingabefolgen (Wörter), die den Automat von einem (oder mehreren) Anfangszuständen in einen von (im allgemeinen) mehreren Endzuständen überführen; die Ausgabe besteht also jeweils nur aus einem Ja oder Nein nach Ende der Eingabe. Symmetrisch dazu werden auch erzeugende Automaten (Generator) betrachtet. Ferner behandelt man nicht nur deterministisch arbeitende Automaten (bei denen die Änderung des jeweiligen Zustands und die jeweilige Ausgabe funktional nur von der momentanen Eingabe und dem aktuellen Zustand abhängt), sondern auch nicht-deterministische Automaten, bei denen Relationen anstelle von Funktionen die mögliche Arbeitsweise beschreiben. Bei der Beschreibung nicht-deterministischer Automaten ist es erlaubt, dass zu einem Paar aus momentaner Eingabe und aktuellem Zustand mehrere mögliche Nachfolgezustände und Angaben angegeben werden, wobei im konkreten Ablauf jeweils nicht-deterministisch eine Wahl getroffen werden muss. So wird also von einem nicht-deterministischen Akzeptor eine Eingabefolge genau dann akzeptiert, wenn sie bei geschickter Auswahl aus den jeweils erlaubten Folgezuständen von einem der Anfangs- zu einem der Endzustände führen kann. Klassen von Akzeptoren entsprechen Klassen von Wortmengen (d.h. formale Sprachen). Die bekannteste Klasseneinteilung bei Akzeptoren erfolgt über die Art der Speicher:

Ursprung

  • griech. automatos - sich von selbst bewegend