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:

  1. ein Eingabealphabet E (eine Menge von Symbolen, auch mit Σ bezeichnet);
  2. ggf. ein Ausgabealphabet A (eine Menge von Symbolen, auch mit Γ bezeichnet);
  3. eine Zustandsmenge Z = {Z0, …, Zn} (auch mit Q bezeichnet);
  4. einen Startzustand Z0 ∈ Z (auch Q0);
  5. eine Endzustandsmenge ZE ⊆ Z (Teilmenge, aber nicht unbedingt echte Teilmenge);
  6. 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
Chomsky-Hierarchie
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
  • Sprache L = anbn (n ist eine natürliche Zahl) mit der Grammatik G = {N,T,S,P}, N = {S}, T = {a,b}, P = {S → ε|aSb}
  • Palindrome (Wörter, die vor- und rückwärts gelesen dasselbe ergeben)
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 losbären Probleme. Beispiele:

  • rekursive Sortieralgorithmen: O(n log n)
  • Suchen: O(n)
  • Gauss-Verfahren O(n3)
Klasse NP
alle Probleme, die sich nicht mit polynomialen Aufwand lösen lassen
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, dass P = NP gilt, ist als Milleniums-Problem mit einer Million Dollar notiert.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.