Automatentheorie
Die Automatentheorie ist ein Teilgebiet der Theoretischen Informatik. Automaten sind einfache Modelle für informationsverarbeitende Maschinen.
Definition eines Automaten
Ein Automat wird über folgende Eigenschaften definiert:
-
- ein Eingabealphabet E (eine Menge von Symbolen, auch mit Σ bezeichnet);
- ggf. ein Ausgabealphabet A (eine Menge von Symbolen, auch mit Γ bezeichnet);
- eine Zustandsmenge Z = {Z0, …, Zn} (auch mit Q bezeichnet);
- einen Startzustand Z0 ∈ Z (auch Q0);
- eine Endzustandsmenge ZE ⊆ Z (Teilmenge, aber nicht unbedingt echte Teilmenge);
- eine Zustandsüberführungsfunktion δ und ggf. eine Ausgabefunktion ω (siehe Klassifikation)
Zustandsübergänge werden durch einen Zustandsübergangsgraphen oder eine Automatentafel dargestellt.
Eine Automatentafel ist eine Tabelle mit dem Zeichen des Eingabealphabets horizontal und den Zuständen vertikal. In den Tabellenzellen wird dann jeweils der Folgezustand angegeben für den Fall, dass in einem Zustand ein bestimmtes Eingabezeichen eingegeben wird. Ggf. kann außerdem noch die Ausgabe beim Erreichen des neuen Zustands angegeben werden.
Außerdem kann man einen Automaten graphisch darstellen: Zustände als Kreise, Endzustände durch Doppelkreise gekennzeichnet, Übergänge durch Pfeile beschriftet mit Übergang.
Klassifikation von Automaten
- Ein Akzeptor (erkennender Automat)
- definiert eine formale Sprache, in dem eine Folge von Eingaben (ein Eingabewort) nur als gültig akzeptiert wird, wenn ein gültiger Endzustand erreicht wird. Der Akzeptor gibt somit einen boolschen Wert zurück (zulässig oder abgelehnt).
- Das Alphabet X der formalen Sprache beinhaltet alle Zeichen der Sprache. Ein Wort w ist eine endliche Menge von Zeichen aus X. Die Menge aller möglichen Wörter heißt X* und beinhaltet auch das leere Wort (dargestellt als ε).
- Zustandsübergänge: Zustand × Zeichen → Folgezustand
- Ein Transduktor
- ist ein Automat mit Ausgaben, die jeweils bei einem Zustandsübergang erfolgen.
- Ein endlicher (finiter) Automat
- hat eine endliche Menge an definierten Zuständen.
- Ein deterministischer Automat
- befindet sich immer in genau einem gespeicherten Zustand.
- Zustandsübergänge: eine Funktion im mathematischen Sinne (alle Zustandübergänge sind eindeutig)
- Ein nicht-deterministischer-Automat
- kann sich gleichzeitig in mehreren Zuständen befinden.
- Zustandübergänge: keine Funktion im mathematischen Sinne, da nicht alle Übergänge eindeutig sind
- Ein deterministischer endlicher Automat (DEA/DFA)
-
-
- Eine Moore-Maschine ist ein DEA, der für jeden erreichten Zustand eine Ausgabe erzeugt.
- Eine Mealy-Maschine ist ein DEA, der mit jeder Eingabe eine Ausgabe erzeugen kann.
-
- Ein nicht-deterministischer endlicher Automat (NEA/NFA)
- kann in einen DEA umgewandelt werden.
- Ein Kellerautomat
- hat zusätzlich noch einen Stack mit einem Startzeichen (Kellervorbelegungszeichen). Die Übergangsfunktion beinhaltet den jetzigen Zustand und das gelesene Zeichen (Eingabezeichen) als Eingaben; die Ausgaben sind der Folgestand, das geschriebene Zeichen (Kellerzeichen) und die Richtung (Kelleroperation). Für die Kelleroperation gibt es folgende Möglichkeiten:
-
- pop entfernt das oberste Kellerelement
- nop legt das oberste Kellerelement wieder auf den Keller
- push ergänzt ein Elemtent zum Keller und behält das vorherige bei
-
- Zustandsübergänge: Zustand × Eingabezeichen × gelesenes Kellerzeichen → Kelleroperation und Folgezustand
- Eine Turing-Maschine
- ist das vereinfachte Modell eines Computers und besitzt nicht einen Stack wie der Kellerautomat, sondern ein Band, auf dem sich der Zeiger in beide Richtungen bewegen kann.
- Zustandsübergänge: Zustand × Eingabezeichen → geschriebenes Zeichen × Bewegungsrichtung × Folgezustand
Grammatiken und Sprachen
Eine Grammatik G = {T,N,S,P} wird definiert durch
-
- eine Menge von Terminalsymbolen T
- eine Menge von Nichtterminalsymbolen N
- ein Startzeichen S
- Produktionsregeln P, welche mögliche Ersetzungen angeben
Sprache | Produktionsregeln der zugehörigen Grammatik | zugehöriger Automat | Beispiel |
---|---|---|---|
Typ 0, RE: rekursiv-aufzählbar | unbeschränkt: beliebige Folge von Terminal- und Nichtterminalsymbolen → beliebige Folge von Terminal- und Nichtterminalsymbolen | Turing-Maschine | |
Typ 1, CS: kontext-sensitiv | y + Nichtterminalsymbol + z → y + beliebige Folge von Terminal- und Nichtterminalsymbolen (außer ε) + z (y und z sind jeweils beliebige Folgen von Terminal- und Nichtterminalsymbolen) |
linear gebundene, nichtdeterministische Turingmaschine (LBA) | Sprache L = anbncn (n ist eine natürliche Zahl) |
Typ 2, CF: kontext-frei | Nichtterminalsymbol → beliebige Folge von Terminal- und Nichtterminalsymbolen | Kellerautomat |
|
Typ 3, REG: regulär | → genau ein Terminalsymbol und maximal ein Nichtterminalsymbol (hier die Reihenfolge bei allen Regeln gleich: immer vor bzw. nach, entspricht links- bzw. rechtsregulär) |
endlicher Automat | Sprache L = a*b* (Anzahlen egal) |
Das Pumping-Lemma dient dazu, zu beweisen, dass eine Sprache nicht regulär ist. Um zu beweisen, dass eine Sprache regulär ist, muss ein endlicher Automat konstruiert werden, der die Sprache akzeptiert.
Eine Funktion ist dann berechenbar, wenn eine Turingmaschine konstruierbar ist, die der Funktion entspricht.
Es gibt keine Turing-Maschine, die entscheiden kann, ob eine beliebige Turing-Maschine nach endlich vielen Schritten anhält oder nicht (unlösbares Halteproblem).
Fleißige Biber
Ein Fleißer Biber ist eine Turing-Maschine mit n Zuständen (n-Biber), die möglichst viele Einsen auf ein Band schreibt und danach anhält.
Die Rado-Funktion ordnet der Anzahl der Zustände die maximale Anzahl an Einsen zu. Die schnell wachsende Funktion ist nicht berechenbar.
Komplexitätsklassen
- Klasse P
- alle mit polynomialen Aufwand von einer deterministischen Turingmaschine losbären Probleme. Beispiele:
-
- rekursive Sortieralgorithmen: O(n log n)
- Suchen: O(n)
- Gauss-Verfahren O(n3)
-
- Klasse NP
- alle mit polynomialen Aufwand von einer nichtdeterministischen Turingmaschine lösbaren Probleme
- Klasse EXP
- alle mit exponentiellen Aufwand lösbaren Probleme. Solche Probleme sind nicht sinnvoll lösbar.
NP-vollständige Probleme sind Probleme der Klasse NP, die nicht in der Klasse P liegen. Der Beweis, ob P = NP gilt, ist als Milleniums-Problem mit einer Million Dollar notiert.