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 = {Z₀, …, Z_n} (auch mit Q bezeichnet);
4. einen Startzustand Z₀ ∈ Z (auch Q₀);
5. eine Endzustandsmenge Z_E ⊆ 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

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(n³)

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.