Automatentheorie
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:
- Endliche Akzeptoren (endliche Automaten) haben endliche Speicherkapazität, die von ihnen akzeptierbaren Wortmengen sind die regulären Sprachen;
- Akzeptoren mit Kellerspeicher (Kellerautomaten) entsprechen kontextfreien Sprachen;
- Akzeptoren mit linear beschränktem Speicher (Linear Beschränkte Automaten) entsprechen kontextsensitiven Sprachen;
- 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
