Automatentheorie

Automatentheorie ist ein Teilgebiet der theoretischen Informatik. Sie beschäftigt sich mit abstrakten Rechenmodellen, sogenannten Automaten. Automaten dienen dazu, Berechnungen formal zu beschreiben und zu untersuchen, welche Arten von Problemen oder Sprachen durch bestimmte Maschinenmodelle erkannt oder entschieden werden können.

Ein Automat kann vereinfacht als mathematisches Modell einer Maschine verstanden werden, die eine Eingabe liest, Zustände wechselt und am Ende entscheidet, ob die Eingabe akzeptiert oder verworfen wird. Die Automatentheorie bildet eine wichtige Grundlage für Formale Sprachen, Compilerbau, Berechenbarkeitstheorie, Komplexitätstheorie, Künstliche Intelligenz, Softwareverifikation und viele weitere Bereiche der Informatik.

Grundidee der Automatentheorie

Die Automatentheorie untersucht, wie sich Berechnungen mit einfachen mathematischen Modellen darstellen lassen. Dabei steht nicht die konkrete technische Umsetzung eines Computers im Vordergrund, sondern die abstrakte Struktur einer Berechnung.

Ein Automat verarbeitet Eingaben schrittweise. Er befindet sich zu jedem Zeitpunkt in einem bestimmten Zustand. Abhängig vom aktuellen Zustand und dem gelesenen Eingabezeichen wechselt er in einen neuen Zustand.

Typische Fragen der Automatentheorie sind:

• Welche Eingaben akzeptiert ein Automat?
• Welche Sprache wird durch einen Automaten erkannt?
• Welcher Automatentyp ist für welche Sprachklasse geeignet?
• Kann ein Automat in ein anderes Modell umgewandelt werden?
• Welche Probleme sind mit einem bestimmten Automatenmodell entscheidbar?
• Welche Grenzen haben einfache Automatenmodelle?

Grundbegriffe

Alphabet

Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen. Es wird meistens mit $\mathrm{\Sigma }$ bezeichnet.

Beispiele:

$\mathrm{\Sigma }=\{0,1\}$

$\mathrm{\Sigma }=\{a,b\}$

$\mathrm{\Sigma }=\{a,b,c,\dots ,z\}$

Ein Alphabet legt fest, aus welchen Zeichen Eingabewörter bestehen dürfen.

Wort

Ein Wort ist eine endliche Folge von Zeichen aus einem Alphabet.

Beispiele über dem Alphabet $\mathrm{\Sigma }=\{0,1\}$:

• $0$
• $1$
• $101$
• $00110$

Das leere Wort wird mit $\epsilon$ bezeichnet. Es enthält kein Zeichen und hat die Länge 0.

Sprache

Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet.

Formal gilt:

$L\subseteq {\mathrm{\Sigma }}^{*}$

Dabei bezeichnet ${\mathrm{\Sigma }}^{*}$ die Menge aller endlichen Wörter über dem Alphabet $\mathrm{\Sigma }$.

Beispiel:

$L=\{w\in \{0,1{\}}^{*}\mid w\text{ endet auf }01\}$

Diese Sprache enthält alle binären Wörter, die auf die Zeichenfolge $01$ enden.

Zustand

Ein Zustand beschreibt die aktuelle interne Situation eines Automaten. Ein Automat besitzt nur endlich viele oder, bei erweiterten Automatenmodellen, formal beschriebene Zustände.

Beispiel:

Ein Automat, der prüfen soll, ob ein Wort auf $01$ endet, muss sich merken, ob zuletzt eine $0$ gelesen wurde und ob danach eine $1$ folgt.

Startzustand

Der Startzustand ist der Zustand, in dem sich ein Automat zu Beginn der Verarbeitung befindet. Er wird häufig mit $q_0$ bezeichnet.

Endzustand

Ein Endzustand oder akzeptierender Zustand ist ein Zustand, in dem der Automat eine Eingabe akzeptiert, wenn die Eingabe vollständig verarbeitet wurde.

Die Menge der Endzustände wird häufig mit $F$ bezeichnet.

Übergangsfunktion

Die Übergangsfunktion beschreibt, wie ein Automat von einem Zustand in einen anderen Zustand wechselt.

Bei einem deterministischen endlichen Automaten hat sie die Form:

$\delta :Q\times \mathrm{\Sigma }\to Q$

Das bedeutet: Für jeden Zustand und jedes Eingabezeichen ist eindeutig festgelegt, welcher Folgezustand erreicht wird.

Automaten als Spracherkenner

In der Automatentheorie betrachtet man Automaten häufig als Spracherkenner. Ein Automat bekommt ein Wort als Eingabe und entscheidet, ob dieses Wort zu einer bestimmten Sprache gehört.

Ein Wort wird akzeptiert, wenn der Automat nach vollständigem Lesen der Eingabe in einem akzeptierenden Zustand endet.

Ein Wort wird verworfen, wenn der Automat nach vollständigem Lesen der Eingabe nicht in einem akzeptierenden Zustand endet.

Beispiel:

Die Sprache

$L=\{w\in \{0,1{\}}^{*}\mid w\text{ enthält eine gerade Anzahl von Einsen}\}$

kann durch einen endlichen Automaten erkannt werden. Der Automat benötigt nur zwei Zustände:

• einen Zustand für „bisher gerade Anzahl von Einsen“,
• einen Zustand für „bisher ungerade Anzahl von Einsen“.

Wichtige Automatenmodelle

Die wichtigsten Automatenmodelle sind:

Automatentyp	Speicher	Erkennt Sprachklasse	Typische Anwendung
Endlicher Automat	Kein zusätzlicher Speicher	Reguläre Sprachen	Mustererkennung, lexikalische Analyse
Kellerautomat	Stapelspeicher	Kontextfreie Sprachen	Syntaxanalyse, Klammerstrukturen
Linear beschränkter Automat	Linear beschränktes Band	Kontext-sensitive Sprachen	theoretische Sprachmodelle
Turingmaschine	Unbeschränktes Band	Rekursiv aufzählbare Sprachen	allgemeines Berechnungsmodell

Endliche Automaten

Ein endlicher Automat ist das einfachste wichtige Automatenmodell. Er besitzt eine endliche Menge von Zuständen und liest ein Eingabewort Zeichen für Zeichen von links nach rechts.

Endliche Automaten haben keinen zusätzlichen Speicher. Sie können sich daher nur endlich viele Informationen über die bisher gelesene Eingabe merken.

Endliche Automaten erkennen genau die regulären Sprachen.

Deterministischer endlicher Automat

Ein deterministischer endlicher Automat, kurz DEA, ist ein Automat, bei dem für jeden Zustand und jedes Eingabezeichen genau ein Folgezustand festgelegt ist.

Ein DEA wird formal als Tupel definiert:

$A=(Q,\mathrm{\Sigma },\delta ,q_0,F)$

Dabei gilt:

Symbol	Bedeutung
$Q$	endliche Menge von Zuständen
$\mathrm{\Sigma }$	Eingabealphabet
$\delta$	Übergangsfunktion
$q_0$	Startzustand
$F$	Menge der akzeptierenden Endzustände

Die Übergangsfunktion lautet:

$\delta :Q\times \mathrm{\Sigma }\to Q$

Arbeitsweise eines DEA

Ein DEA arbeitet folgendermaßen:

1. Der Automat startet im Startzustand $q_0$.
2. Er liest das Eingabewort von links nach rechts.
3. Für jedes Zeichen wird anhand der Übergangsfunktion der nächste Zustand bestimmt.
4. Nach dem letzten Zeichen wird geprüft, ob der aktuelle Zustand ein Endzustand ist.
5. Ist der Zustand ein Endzustand, wird das Wort akzeptiert.
6. Andernfalls wird das Wort verworfen.

Beispiel eines DEA

Gesucht ist ein Automat über dem Alphabet

$\mathrm{\Sigma }=\{0,1\}$

der alle Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten.

Die Zustände sind:

Zustand	Bedeutung
$q_0$	bisher gerade Anzahl von Einsen gelesen
$q_1$	bisher ungerade Anzahl von Einsen gelesen

Der Startzustand ist $q_0$. Gleichzeitig ist $q_0$ auch der einzige Endzustand.

Die Übergangstabelle lautet:

Aktueller Zustand	Eingabe 0	Eingabe 1
$q_0$	$q_0$	$q_1$
$q_1$	$q_1$	$q_0$

Eine gelesene $0$ ändert die Anzahl der Einsen nicht. Eine gelesene $1$ wechselt zwischen gerade und ungerade.

Nichtdeterministischer endlicher Automat

Ein nichtdeterministischer endlicher Automat, kurz NEA, erlaubt für einen Zustand und ein Eingabezeichen mehrere mögliche Folgezustände.

Die Übergangsfunktion eines NEA hat die Form:

$\delta :Q\times \mathrm{\Sigma }\to {𝒫}(Q)$

Dabei bezeichnet ${𝒫}(Q)$ die Potenzmenge von $Q$, also die Menge aller Teilmengen von $Q$.

Ein NEA akzeptiert ein Wort, wenn es mindestens einen möglichen Rechenweg gibt, der in einem akzeptierenden Zustand endet.

Unterschied zwischen DEA und NEA

Eigenschaft	DEA	NEA
Folgezustand	eindeutig bestimmt	mehrere Möglichkeiten erlaubt
Berechnung	genau ein Rechenweg	mehrere mögliche Rechenwege
Akzeptanz	Endzustand nach eindeutigem Lauf	mindestens ein akzeptierender Lauf genügt
Ausdrucksstärke	reguläre Sprachen	reguläre Sprachen

Obwohl ein NEA flexibler wirkt, ist er nicht mächtiger als ein DEA. Jeder NEA kann in einen äquivalenten DEA umgewandelt werden. Dieses Verfahren heißt Potenzmengenkonstruktion.

Epsilon-NEA

Ein Epsilon-NEA ist ein nichtdeterministischer endlicher Automat, der zusätzlich sogenannte $\epsilon$-Übergänge erlaubt.

Ein $\epsilon$-Übergang ist ein Zustandswechsel, bei dem kein Eingabezeichen gelesen wird.

Die Übergangsfunktion lautet:

$\delta :Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\to {𝒫}(Q)$

Auch Epsilon-NEAs erkennen genau die regulären Sprachen.

Reguläre Sprachen

Eine Sprache heißt regulär, wenn sie durch einen endlichen Automaten erkannt werden kann.

Reguläre Sprachen können äquivalent beschrieben werden durch:

• deterministische endliche Automaten,
• nichtdeterministische endliche Automaten,
• Epsilon-NEAs,
• reguläre Ausdrücke,
• reguläre Grammatiken.

Beispiele regulärer Sprachen

Über dem Alphabet $\mathrm{\Sigma }=\{0,1\}$ sind folgende Sprachen regulär:

• alle Wörter, die mit $0$ beginnen,
• alle Wörter, die auf $101$ enden,
• alle Wörter mit gerader Anzahl von Einsen,
• alle Wörter, die die Teilfolge $00$ enthalten,
• alle Wörter mit höchstens drei Zeichen.

Reguläre Ausdrücke

Ein regulärer Ausdruck beschreibt eine reguläre Sprache durch eine formale Schreibweise.

Wichtige Operationen sind:

Schreibweise	Bedeutung
$a$	das Zeichen $a$
$r\mid s$	Alternative: $r$ oder $s$
$rs$	Konkatenation von $r$ und $s$
$r^{*}$	beliebig viele Wiederholungen von $r$
$\epsilon$	leeres Wort
$\mathrm{\varnothing }$	leere Sprache

Beispiel:

$(0\mid 1{)}^{*}101$

Dieser reguläre Ausdruck beschreibt alle binären Wörter, die auf $101$ enden.

Äquivalenz von Automaten und regulären Ausdrücken

Ein wichtiger Satz der Automatentheorie lautet:

Eine Sprache ist genau dann regulär, wenn sie von einem endlichen Automaten erkannt werden kann.

Gleichwertig gilt:

Eine Sprache ist genau dann regulär, wenn sie durch einen regulären Ausdruck beschrieben werden kann.

Das bedeutet, dass endliche Automaten und reguläre Ausdrücke dieselbe Ausdrucksstärke besitzen.

Potenzmengenkonstruktion

Die Potenzmengenkonstruktion ist ein Verfahren zur Umwandlung eines NEA in einen äquivalenten DEA.

Die Grundidee ist, dass ein Zustand des neuen DEA einer Menge von möglichen Zuständen des NEA entspricht.

Wenn der NEA die Zustände

$Q=\{q_0,q_1,q_2\}$

hat, dann können die Zustände des konstruierten DEA Teilmengen davon sein, zum Beispiel:

• $\mathrm{\varnothing }$
• $\{q_0\}$
• $\{q_1\}$
• $\{q_0,q_1\}$
• $\{q_0,q_2\}$
• $\{q_0,q_1,q_2\}$

Der neue DEA simuliert also gleichzeitig alle möglichen Rechenwege des NEA.

Minimierung endlicher Automaten

Die Automatenminimierung beschäftigt sich damit, zu einem gegebenen endlichen Automaten einen äquivalenten Automaten mit möglichst wenigen Zuständen zu finden.

Zwei Zustände heißen äquivalent, wenn sie für alle möglichen Fortsetzungen der Eingabe dasselbe Akzeptanzverhalten besitzen.

Ein minimaler DEA besitzt keine unterscheidbaren Zustände, die zusammengelegt werden können.

Bedeutung der Minimierung

Die Minimierung ist wichtig, weil sie Automaten vereinfacht und effizienter macht.

Anwendungen:

• Optimierung von lexikalischen Scannern,
• Reduktion von Zustandsautomaten,
• formale Verifikation,
• Mustererkennung,
• Protokollanalyse.

Myhill-Nerode-Theorem

Das Myhill-Nerode-Theorem ist ein grundlegender Satz über reguläre Sprachen.

Es charakterisiert reguläre Sprachen über Äquivalenzklassen von Wörtern. Vereinfacht besagt es:

Eine Sprache ist genau dann regulär, wenn sie nur endlich viele unterscheidbare Restsprachen besitzt.

Anschaulich bedeutet das: Ein endlicher Automat kann nur endlich viele verschiedene Situationen unterscheiden. Wenn eine Sprache unendlich viele wirklich verschiedene Merksituationen benötigt, ist sie nicht regulär.

Das Myhill-Nerode-Theorem wird verwendet, um:

• die Regularität einer Sprache zu charakterisieren,
• minimale Automaten zu bestimmen,
• zu beweisen, dass bestimmte Sprachen nicht regulär sind.

Pumping-Lemma für reguläre Sprachen

Das Pumping-Lemma ist ein Werkzeug, um zu zeigen, dass eine Sprache nicht regulär ist.

Es besagt vereinfacht:

Wenn eine Sprache regulär ist, dann gibt es eine Zahl $p$, sodass jedes Wort $w$ der Sprache mit $|w|\ge p$ in drei Teile $w=xyz$ zerlegt werden kann, wobei der mittlere Teil $y$ beliebig oft wiederholt werden darf und das Wort trotzdem in der Sprache bleibt.

Formal gilt für reguläre Sprachen:

$w=xyz$

mit:

• $|xy|\le p$,
• $|y|>0$,
• $x{y}^{i}z\in L$ für alle $i\ge 0$.

Beispiel: Nicht-Regularität von a^n b^n

Die Sprache

$L=\{a^n{b}^n\mid n\ge 0\}$

ist nicht regulär.

Ein endlicher Automat kann nicht beliebig viele $a$-Zeichen zählen, um anschließend genau dieselbe Anzahl von $b$-Zeichen zu überprüfen. Dafür wäre ein unbeschränkter Speicher erforderlich.

Kellerautomaten

Ein Kellerautomat ist ein Automat mit zusätzlichem Stapelspeicher. Dieser Stapel wird auch Keller genannt.

Ein Kellerautomat kann:

• Eingabezeichen lesen,
• Zustände wechseln,
• Symbole auf den Stapel legen,
• Symbole vom Stapel entfernen,
• das oberste Stapelsymbol betrachten.

Kellerautomaten erkennen genau die kontextfreien Sprachen.

Aufbau eines Kellerautomaten

Ein Kellerautomat wird häufig als Tupel beschrieben:

$A=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,Z_0,F)$

Dabei gilt:

Symbol	Bedeutung
$Q$	endliche Zustandsmenge
$\mathrm{\Sigma }$	Eingabealphabet
$\mathrm{\Gamma }$	Kelleralphabet
$\delta$	Übergangsfunktion
$q_0$	Startzustand
$Z_0$	Startsymbol im Keller
$F$	Menge akzeptierender Zustände

Beispiel für eine kontextfreie Sprache

Die Sprache

$L=\{a^n{b}^n\mid n\ge 0\}$

kann durch einen Kellerautomaten erkannt werden.

Die Idee ist:

1. Für jedes gelesene $a$ legt der Automat ein Symbol auf den Keller.
2. Für jedes gelesene $b$ entfernt der Automat ein Symbol vom Keller.
3. Am Ende wird akzeptiert, wenn der Keller wieder leer ist beziehungsweise nur noch das Startsymbol enthält.

Dadurch kann der Kellerautomat die Anzahl der $a$-Zeichen mit der Anzahl der $b$-Zeichen vergleichen.

Deterministische und nichtdeterministische Kellerautomaten

Bei endlichen Automaten sind deterministische und nichtdeterministische Varianten gleich mächtig. Bei Kellerautomaten ist das anders.

Ein nichtdeterministischer Kellerautomat ist mächtiger als ein deterministischer Kellerautomat.

Das bedeutet:

• Nichtdeterministische Kellerautomaten erkennen alle kontextfreien Sprachen.
• Deterministische Kellerautomaten erkennen nur eine echte Teilklasse der kontextfreien Sprachen.

Diese Unterscheidung ist besonders im Compilerbau relevant. Viele Programmiersprachen sind so gestaltet, dass ihre Syntax deterministisch analysierbar ist.

Turingmaschinen

Eine Turingmaschine ist ein sehr mächtiges abstraktes Berechnungsmodell. Sie wurde von Alan Turing eingeführt und gilt als formales Modell allgemeiner Berechenbarkeit.

Eine Turingmaschine besteht aus:

• einer endlichen Zustandsmenge,
• einem Band mit Speicherzellen,
• einem Schreib-/Lesekopf,
• einem Eingabealphabet,
• einem Bandalphabet,
• einer Übergangsfunktion,
• einem Startzustand,
• akzeptierenden und verwerfenden Zuständen.

Im Gegensatz zu endlichen Automaten und Kellerautomaten kann eine Turingmaschine auf ihrem Band lesen und schreiben. Der Schreib-/Lesekopf kann sich nach links und rechts bewegen.

Formaler Aufbau einer Turingmaschine

Eine Turingmaschine kann als Tupel beschrieben werden:

$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{accept},q_{reject})$

Dabei gilt:

Symbol	Bedeutung
$Q$	endliche Menge von Zuständen
$\mathrm{\Sigma }$	Eingabealphabet
$\mathrm{\Gamma }$	Bandalphabet
$\delta$	Übergangsfunktion
$q_0$	Startzustand
$q_{accept}$	akzeptierender Zustand
$q_{reject}$	verwerfender Zustand

Die Übergangsfunktion hat häufig die Form:

$\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$

Das bedeutet: Abhängig vom aktuellen Zustand und dem gelesenen Bandsymbol schreibt die Turingmaschine ein neues Symbol, wechselt den Zustand und bewegt den Kopf nach links oder rechts.

Bedeutung der Turingmaschine

Die Turingmaschine ist eines der wichtigsten Modelle der Informatik, weil sie die theoretische Grenze algorithmischer Berechenbarkeit beschreibt.

Nach der Church-Turing-These gilt:

Alles, was intuitiv algorithmisch berechenbar ist, kann auch von einer Turingmaschine berechnet werden.

Die Turingmaschine ist damit nicht nur ein Automatenmodell, sondern auch ein Fundament der Berechenbarkeitstheorie.

Entscheidbare und akzeptierbare Sprachen

Im Zusammenhang mit Turingmaschinen unterscheidet man häufig zwischen entscheidbaren und akzeptierbaren Sprachen.

Entscheidbare Sprache

Eine Sprache heißt entscheidbar, wenn es eine Turingmaschine gibt, die für jedes Eingabewort nach endlich vielen Schritten anhält und korrekt entscheidet, ob das Wort zur Sprache gehört.

Akzeptierbare Sprache

Eine Sprache heißt akzeptierbar oder rekursiv aufzählbar, wenn es eine Turingmaschine gibt, die jedes Wort der Sprache akzeptiert. Für Wörter, die nicht zur Sprache gehören, muss sie jedoch nicht unbedingt anhalten.

Jede entscheidbare Sprache ist akzeptierbar, aber nicht jede akzeptierbare Sprache ist entscheidbar.

Das Halteproblem

Das Halteproblem ist ein klassisches Beispiel für ein unentscheidbares Problem.

Es fragt:

Hält ein gegebenes Programm bei einer gegebenen Eingabe nach endlich vielen Schritten an?

Alan Turing zeigte, dass es keinen allgemeinen Algorithmus geben kann, der diese Frage für alle Programme und Eingaben korrekt beantwortet.

Das Halteproblem zeigt eine fundamentale Grenze automatischer Berechnung.

Linear beschränkte Automaten

Ein linear beschränkter Automat ist eine eingeschränkte Turingmaschine. Sein Band ist nur linear in der Länge der Eingabe beschränkt.

Linear beschränkte Automaten erkennen die kontext-sensitiven Sprachen.

Sie stehen in der Chomsky-Hierarchie zwischen Kellerautomaten und allgemeinen Turingmaschinen.

Chomsky-Hierarchie und Automaten

Die Chomsky-Hierarchie ordnet formale Sprachen nach ihrer Ausdrucksstärke. Jeder Sprachklasse entspricht ein bestimmtes Automatenmodell.

Typ	Sprachklasse	Grammatik	Automatenmodell
Typ 3	Reguläre Sprachen	Reguläre Grammatiken	Endliche Automaten
Typ 2	Kontextfreie Sprachen	Kontextfreie Grammatiken	Kellerautomaten
Typ 1	Kontext-sensitive Sprachen	Kontext-sensitive Grammatiken	Linear beschränkte Automaten
Typ 0	Rekursiv aufzählbare Sprachen	Unbeschränkte Grammatiken	Turingmaschinen

Die Hierarchie zeigt, dass mächtigere Automatenmodelle größere Sprachklassen erkennen können.

Vergleich wichtiger Automatenmodelle

Eigenschaft	Endlicher Automat	Kellerautomat	Turingmaschine
Zustände	endlich	endlich	endlich
Zusätzlicher Speicher	keiner	Stapel	unbeschränktes Band
Speicherzugriff	nicht vorhanden	nur oberstes Stapelsymbol	beliebige Bandbewegung schrittweise
Erkannte Sprachen	regulär	kontextfrei	rekursiv aufzählbar
Beispielproblem	Wort endet auf 01	gleich viele a und b in Form a^n b^n	allgemeine Berechnung
Ausdrucksstärke	gering	mittel	sehr hoch

Abschluss- und Entscheidungsprobleme

In der Automatentheorie werden häufig Entscheidungsprobleme über Automaten und Sprachen untersucht.

Typische Fragen sind:

• Ist die Sprache eines Automaten leer?
• Sind zwei Automaten äquivalent?
• Akzeptiert ein Automat ein bestimmtes Wort?
• Ist eine Sprache regulär?
• Ist eine Grammatik mehrdeutig?
• Hält eine Turingmaschine auf einer bestimmten Eingabe?

Einige dieser Probleme sind entscheidbar, andere nicht.

Leerheitsproblem

Das Leerheitsproblem fragt, ob die von einem Automaten erkannte Sprache leer ist.

Für endliche Automaten lautet die Frage:

Gibt es mindestens ein Wort, das vom Automaten akzeptiert wird?

Bei endlichen Automaten ist dieses Problem entscheidbar. Man prüft, ob ein Endzustand vom Startzustand aus erreichbar ist.

Wortproblem

Das Wortproblem fragt, ob ein bestimmtes Wort von einem Automaten akzeptiert wird.

Für endliche Automaten ist das Wortproblem leicht entscheidbar: Man simuliert den Automaten auf dem Eingabewort.

Auch für Kellerautomaten und Turingmaschinen kann man entsprechende Varianten betrachten. Bei Turingmaschinen kann das Wortproblem jedoch problematisch werden, wenn die Maschine auf manchen Eingaben nicht anhält.

Äquivalenzproblem

Das Äquivalenzproblem fragt, ob zwei Automaten dieselbe Sprache erkennen.

Für deterministische endliche Automaten ist das Äquivalenzproblem entscheidbar.

Die Frage lautet:

Gilt $L(A_1)=L(A_2)$?

Man kann dies zum Beispiel prüfen, indem man einen Produktautomaten konstruiert und untersucht, ob es ein Wort gibt, das von genau einem der beiden Automaten akzeptiert wird.

Produktautomat

Ein Produktautomat kombiniert zwei Automaten zu einem neuen Automaten. Er wird häufig verwendet, um Abschlussoperationen oder Entscheidungsprobleme zu untersuchen.

Wenn zwei Automaten die Zustandsmengen $Q_1$ und $Q_2$ besitzen, dann hat der Produktautomat Zustände der Form:

$(q_1,q_2)$

mit:

$q_1\in Q_1$ und $q_2\in Q_2$.

Der Produktautomat simuliert beide Automaten gleichzeitig.

Abschlusseigenschaften regulärer Sprachen

Reguläre Sprachen sind unter vielen Operationen abgeschlossen. Das bedeutet: Wenn man reguläre Sprachen mit bestimmten Operationen kombiniert, entsteht wieder eine reguläre Sprache.

Reguläre Sprachen sind abgeschlossen unter:

• Vereinigung,
• Schnitt,
• Komplement,
• Differenz,
• Konkatenation,
• Kleene-Stern,
• Spiegelung.

Diese Eigenschaften lassen sich häufig mit Automatenkonstruktionen beweisen.

Beispiel: Vereinigung regulärer Sprachen

Seien $L_1$ und $L_2$ reguläre Sprachen.

Dann ist auch

$L_1\cup L_2$

regulär.

Begründung: Man kann einen Produktautomaten konstruieren, der beide Automaten parallel simuliert. Der neue Automat akzeptiert, wenn mindestens einer der beiden ursprünglichen Automaten akzeptiert.

Beispiel: Schnitt regulärer Sprachen

Seien $L_1$ und $L_2$ reguläre Sprachen.

Dann ist auch

$L_1\cap L_2$

regulär.

Der Produktautomat akzeptiert in diesem Fall nur dann, wenn beide ursprünglichen Automaten akzeptieren.

Typische Beweismethoden

In der Automatentheorie werden verschiedene mathematische Beweismethoden eingesetzt.

Wichtige Methoden sind:

• Konstruktion eines Automaten,
• Angabe einer Übergangstabelle,
• Induktionsbeweis über die Länge des Eingabewortes,
• Pumping-Lemma-Beweis,
• Myhill-Nerode-Argument,
• Reduktion,
• Simulation eines Automatenmodells durch ein anderes.

Typische Klausuraufgaben

Typische Aufgaben zur Automatentheorie sind:

• Konstruieren Sie einen DEA zu einer gegebenen Sprache.
• Geben Sie einen regulären Ausdruck zu einem Automaten an.
• Wandeln Sie einen NEA in einen DEA um.
• Minimieren Sie einen endlichen Automaten.
• Entscheiden Sie, ob eine Sprache regulär ist.
• Zeigen Sie mit dem Pumping-Lemma, dass eine Sprache nicht regulär ist.
• Konstruieren Sie einen Kellerautomaten für eine kontextfreie Sprache.
• Geben Sie eine Grammatik zu einem Automaten an.
• Ordnen Sie eine Sprache in die Chomsky-Hierarchie ein.
• Erklären Sie den Unterschied zwischen DEA, NEA und Epsilon-NEA.
• Beschreiben Sie die Arbeitsweise einer Turingmaschine.
• Zeigen Sie, dass ein Problem entscheidbar oder unentscheidbar ist.

Anwendungsbereiche

Obwohl Automaten abstrakte Modelle sind, haben sie viele praktische Anwendungen.

Bereich	Anwendung der Automatentheorie
Compilerbau	lexikalische Analyse und Syntaxanalyse
Reguläre Ausdrücke	Suchmuster in Texten
Protokolle	Modellierung von Zustandsübergängen
Softwareverifikation	Prüfung von Programmzuständen
Hardwareentwurf	Modellierung digitaler Schaltungen
Datenbanken	Anfrageverarbeitung und formale Logik
Sprachverarbeitung	formale Beschreibung syntaktischer Strukturen
Künstliche Intelligenz	Zustandsräume und Suchverfahren

Beispiel aus dem Compilerbau

Im Compilerbau werden endliche Automaten häufig für die lexikalische Analyse verwendet.

Ein Scanner zerlegt Quelltext in sogenannte Token. Beispiele für Token sind:

• Schlüsselwörter,
• Bezeichner,
• Zahlen,
• Operatoren,
• Klammern.

Reguläre Ausdrücke beschreiben dabei die Struktur der Token. Aus diesen regulären Ausdrücken können endliche Automaten erzeugt werden, die den Quelltext effizient erkennen.

Ein Bezeichner in einer Programmiersprache könnte zum Beispiel durch folgenden regulären Ausdruck beschrieben werden:

$[a-zA-Z][a-zA-Z0-9{]}^{*}$

Dieser Ausdruck beschreibt Wörter, die mit einem Buchstaben beginnen und danach aus Buchstaben oder Ziffern bestehen.

Beispiel aus der Protokollmodellierung

Kommunikationsprotokolle lassen sich als Zustandsautomaten beschreiben.

Ein stark vereinfachter Verbindungsaufbau könnte folgende Zustände besitzen:

Zustand	Bedeutung
CLOSED	keine Verbindung
LISTEN	wartet auf Verbindung
SYN_RECEIVED	Verbindungsanfrage empfangen
ESTABLISHED	Verbindung aufgebaut

Übergänge entstehen durch Ereignisse wie eingehende Pakete, Zeitüberschreitungen oder Benutzeraktionen.

Grenzen einfacher Automaten

Endliche Automaten sind sehr effizient, aber in ihrer Ausdrucksstärke beschränkt. Sie können keine beliebig großen Mengen zählen oder verschachtelte Strukturen allgemeiner Tiefe erkennen.

Nicht regulär sind zum Beispiel Sprachen wie:

$L=\{a^n{b}^n\mid n\ge 0\}$

oder:

$L=\{ww\mid w\in \{0,1{\}}^{*}\}$

Solche Sprachen erfordern mehr Speicher als ein endlicher Automat besitzt.

Zusammenhang mit Berechenbarkeit und Komplexität

Die Automatentheorie bildet eine Brücke zwischen formalen Sprachen, Berechenbarkeit und Komplexität.

• Endliche Automaten zeigen, welche Sprachen mit sehr begrenztem Speicher erkannt werden können.
• Kellerautomaten erweitern dieses Modell um Stapelspeicher.
• Turingmaschinen beschreiben allgemeine Berechenbarkeit.
• Die Komplexitätstheorie untersucht anschließend, wie viele Ressourcen eine Berechnung benötigt.

Damit ist die Automatentheorie eine Grundlage für das Verständnis der Frage, was Computer prinzipiell leisten können und wo ihre Grenzen liegen.

Wichtige Begriffe

Begriff	Erklärung
Automat	abstraktes mathematisches Modell einer berechnenden Maschine
Zustand	interne Situation eines Automaten
Startzustand	Zustand, in dem die Verarbeitung beginnt
Endzustand	akzeptierender Zustand eines Automaten
Übergangsfunktion	Regel für Zustandswechsel
DEA	deterministischer endlicher Automat
NEA	nichtdeterministischer endlicher Automat
Epsilon-Übergang	Zustandswechsel ohne Lesen eines Eingabezeichens
Reguläre Sprache	Sprache, die von einem endlichen Automaten erkannt wird
Kellerautomat	Automat mit Stapelspeicher
Turingmaschine	allgemeines Modell algorithmischer Berechnung
Chomsky-Hierarchie	Klassifikation formaler Sprachen
Pumping-Lemma	Werkzeug zum Nachweis, dass eine Sprache nicht regulär ist
Potenzmengenkonstruktion	Verfahren zur Umwandlung eines NEA in einen DEA

Zusammenfassung

Die Automatentheorie untersucht abstrakte Maschinenmodelle und deren Fähigkeit, formale Sprachen zu erkennen. Sie beginnt bei einfachen endlichen Automaten, die reguläre Sprachen erkennen, und reicht über Kellerautomaten bis hin zu Turingmaschinen als allgemeinem Berechnungsmodell.

Endliche Automaten sind besonders wichtig für reguläre Sprachen und praktische Anwendungen wie reguläre Ausdrücke, Scanner und Protokollmodellierung. Kellerautomaten erweitern dieses Modell um einen Stapelspeicher und können dadurch kontextfreie Sprachen erkennen. Turingmaschinen bilden schließlich ein umfassendes Modell für algorithmische Berechnung.

Die Automatentheorie zeigt damit sowohl die Möglichkeiten als auch die Grenzen formaler Berechnungsmodelle. Sie ist ein zentrales Fundament der theoretischen Informatik und eng mit formalen Sprachen, Berechenbarkeitstheorie und Komplexitätstheorie verbunden.

Siehe auch

• Theoretische Informatik
• Formale Sprachen
• Reguläre Sprachen
• Reguläre Ausdrücke
• Deterministischer endlicher Automat
• Nichtdeterministischer endlicher Automat
• Kellerautomat
• Turingmaschine
• Chomsky-Hierarchie
• Berechenbarkeitstheorie
• Komplexitätstheorie
• Pumping-Lemma
• Myhill-Nerode-Theorem