PhilKa: Die Seite wurde neu angelegt: „{{Infobox Fachgebiet | Name = Automatentheorie | Gebiet = Theoretische Informatik | Zentrale Objekte = Automaten, Zustände, Übergänge, formale Sprachen | Wichtige Modelle = Endliche Automaten, Kellerautomaten, Turingmaschinen, linear beschränkte Automaten | Verwandte Themen = Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Compilerbau }} '''Automatentheorie''' ist ein Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]…“

2026-04-30T10:16:55Z

Die Seite wurde neu angelegt: „{{Infobox Fachgebiet | Name = Automatentheorie | Gebiet = Theoretische Informatik | Zentrale Objekte = Automaten, Zustände, Übergänge, formale Sprachen | Wichtige Modelle = Endliche Automaten, Kellerautomaten, Turingmaschinen, linear beschränkte Automaten | Verwandte Themen = Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Compilerbau }} '''Automatentheorie''' ist ein Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]…“

Neue Seite

{{Infobox Fachgebiet
| Name = Automatentheorie
| Gebiet = Theoretische Informatik
| Zentrale Objekte = Automaten, Zustände, Übergänge, formale Sprachen
| Wichtige Modelle = Endliche Automaten, Kellerautomaten, Turingmaschinen, linear beschränkte Automaten
| Verwandte Themen = Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Compilerbau
}}

'''Automatentheorie''' ist ein Teilgebiet der [[Theoretische Informatik|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 <math>\Sigma</math> bezeichnet.

Beispiele:

<math>\Sigma = \{0,1\}</math>

<math>\Sigma = \{a,b\}</math>

<math>\Sigma = \{a,b,c,\dots,z\}</math>

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 <math>\Sigma = \{0,1\}</math>:

* <math>0</math>
* <math>1</math>
* <math>101</math>
* <math>00110</math>

Das leere Wort wird mit <math>\varepsilon</math> 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:

<math>L \subseteq \Sigma^*</math>

Dabei bezeichnet <math>\Sigma^*</math> die Menge aller endlichen Wörter über dem Alphabet <math>\Sigma</math>.

Beispiel:

<math>L = \{w \in \{0,1\}^* \mid w \text{ endet auf } 01\}</math>

Diese Sprache enthält alle binären Wörter, die auf die Zeichenfolge <math>01</math> 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 <math>01</math> endet, muss sich merken, ob zuletzt eine <math>0</math> gelesen wurde und ob danach eine <math>1</math> folgt.

=== Startzustand ===

Der '''Startzustand''' ist der Zustand, in dem sich ein Automat zu Beginn der Verarbeitung befindet. Er wird häufig mit <math>q_0</math> 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 <math>F</math> 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:

<math>\delta : Q \times \Sigma \rightarrow Q</math>

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

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

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:

{| class="wikitable"
! 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:

<math>A = (Q, \Sigma, \delta, q_0, F)</math>

Dabei gilt:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>Q</math>
| endliche Menge von Zuständen
|-
| <math>\Sigma</math>
| Eingabealphabet
|-
| <math>\delta</math>
| Übergangsfunktion
|-
| <math>q_0</math>
| Startzustand
|-
| <math>F</math>
| Menge der akzeptierenden Endzustände
|}

Die Übergangsfunktion lautet:

<math>\delta : Q \times \Sigma \rightarrow Q</math>

=== Arbeitsweise eines DEA ===

Ein DEA arbeitet folgendermaßen:

# Der Automat startet im Startzustand <math>q_0</math>.
# Er liest das Eingabewort von links nach rechts.
# Für jedes Zeichen wird anhand der Übergangsfunktion der nächste Zustand bestimmt.
# Nach dem letzten Zeichen wird geprüft, ob der aktuelle Zustand ein Endzustand ist.
# Ist der Zustand ein Endzustand, wird das Wort akzeptiert.
# Andernfalls wird das Wort verworfen.

=== Beispiel eines DEA ===

Gesucht ist ein Automat über dem Alphabet

<math>\Sigma = \{0,1\}</math>

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

Die Zustände sind:

{| class="wikitable"
! Zustand
! Bedeutung
|-
| <math>q_0</math>
| bisher gerade Anzahl von Einsen gelesen
|-
| <math>q_1</math>
| bisher ungerade Anzahl von Einsen gelesen
|}

Der Startzustand ist <math>q_0</math>. Gleichzeitig ist <math>q_0</math> auch der einzige Endzustand.

Die Übergangstabelle lautet:

{| class="wikitable"
! Aktueller Zustand
! Eingabe 0
! Eingabe 1
|-
| <math>q_0</math>
| <math>q_0</math>
| <math>q_1</math>
|-
| <math>q_1</math>
| <math>q_1</math>
| <math>q_0</math>
|}

Eine gelesene <math>0</math> ändert die Anzahl der Einsen nicht. Eine gelesene <math>1</math> 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:

<math>\delta : Q \times \Sigma \rightarrow \mathcal{P}(Q)</math>

Dabei bezeichnet <math>\mathcal{P}(Q)</math> die Potenzmenge von <math>Q</math>, also die Menge aller Teilmengen von <math>Q</math>.

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

=== Unterschied zwischen DEA und NEA ===

{| class="wikitable"
! 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 <math>\varepsilon</math>-Übergänge erlaubt.

Ein <math>\varepsilon</math>-Übergang ist ein Zustandswechsel, bei dem kein Eingabezeichen gelesen wird.

Die Übergangsfunktion lautet:

<math>\delta : Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow \mathcal{P}(Q)</math>

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 <math>\Sigma = \{0,1\}</math> sind folgende Sprachen regulär:

* alle Wörter, die mit <math>0</math> beginnen,
* alle Wörter, die auf <math>101</math> enden,
* alle Wörter mit gerader Anzahl von Einsen,
* alle Wörter, die die Teilfolge <math>00</math> 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:

{| class="wikitable"
! Schreibweise
! Bedeutung
|-
| <math>a</math>
| das Zeichen <math>a</math>
|-
| <math>r \mid s</math>
| Alternative: <math>r</math> oder <math>s</math>
|-
| <math>rs</math>
| Konkatenation von <math>r</math> und <math>s</math>
|-
| <math>r^*</math>
| beliebig viele Wiederholungen von <math>r</math>
|-
| <math>\varepsilon</math>
| leeres Wort
|-
| <math>\emptyset</math>
| leere Sprache
|}

Beispiel:

<math>(0 \mid 1)^*101</math>

Dieser reguläre Ausdruck beschreibt alle binären Wörter, die auf <math>101</math> 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

<math>Q = \{q_0, q_1, q_2\}</math>

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

* <math>\emptyset</math>
* <math>\{q_0\}</math>
* <math>\{q_1\}</math>
* <math>\{q_0, q_1\}</math>
* <math>\{q_0, q_2\}</math>
* <math>\{q_0, q_1, q_2\}</math>

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 <math>p</math>, sodass jedes Wort <math>w</math> der Sprache mit <math>|w| \geq p</math> in drei Teile <math>w = xyz</math> zerlegt werden kann, wobei der mittlere Teil <math>y</math> beliebig oft wiederholt werden darf und das Wort trotzdem in der Sprache bleibt.

Formal gilt für reguläre Sprachen:

<math>w = xyz</math>

mit:

* <math>|xy| \leq p</math>,
* <math>|y| > 0</math>,
* <math>xy^iz \in L</math> für alle <math>i \geq 0</math>.

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

Die Sprache

<math>L = \{a^n b^n \mid n \geq 0\}</math>

ist nicht regulär.

Ein endlicher Automat kann nicht beliebig viele <math>a</math>-Zeichen zählen, um anschließend genau dieselbe Anzahl von <math>b</math>-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:

<math>A = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)</math>

Dabei gilt:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>Q</math>
| endliche Zustandsmenge
|-
| <math>\Sigma</math>
| Eingabealphabet
|-
| <math>\Gamma</math>
| Kelleralphabet
|-
| <math>\delta</math>
| Übergangsfunktion
|-
| <math>q_0</math>
| Startzustand
|-
| <math>Z_0</math>
| Startsymbol im Keller
|-
| <math>F</math>
| Menge akzeptierender Zustände
|}

=== Beispiel für eine kontextfreie Sprache ===

Die Sprache

<math>L = \{a^n b^n \mid n \geq 0\}</math>

kann durch einen Kellerautomaten erkannt werden.

Die Idee ist:

# Für jedes gelesene <math>a</math> legt der Automat ein Symbol auf den Keller.
# Für jedes gelesene <math>b</math> entfernt der Automat ein Symbol vom Keller.
# Am Ende wird akzeptiert, wenn der Keller wieder leer ist beziehungsweise nur noch das Startsymbol enthält.

Dadurch kann der Kellerautomat die Anzahl der <math>a</math>-Zeichen mit der Anzahl der <math>b</math>-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:

<math>M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})</math>

Dabei gilt:

{| class="wikitable"
! Symbol
! Bedeutung
|-
| <math>Q</math>
| endliche Menge von Zuständen
|-
| <math>\Sigma</math>
| Eingabealphabet
|-
| <math>\Gamma</math>
| Bandalphabet
|-
| <math>\delta</math>
| Übergangsfunktion
|-
| <math>q_0</math>
| Startzustand
|-
| <math>q_{accept}</math>
| akzeptierender Zustand
|-
| <math>q_{reject}</math>
| verwerfender Zustand
|}

Die Übergangsfunktion hat häufig die Form:

<math>\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math>

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.

{| class="wikitable"
! 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 ==

{| class="wikitable"
! 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 <math>L(A_1) = L(A_2)</math>?

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 <math>Q_1</math> und <math>Q_2</math> besitzen, dann hat der Produktautomat Zustände der Form:

<math>(q_1, q_2)</math>

mit:

<math>q_1 \in Q_1</math> und <math>q_2 \in Q_2</math>.

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 <math>L_1</math> und <math>L_2</math> reguläre Sprachen.

Dann ist auch

<math>L_1 \cup L_2</math>

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 <math>L_1</math> und <math>L_2</math> reguläre Sprachen.

Dann ist auch

<math>L_1 \cap L_2</math>

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.

{| class="wikitable"
! 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:

<math>[a-zA-Z][a-zA-Z0-9]^*</math>

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:

{| class="wikitable"
! 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:

<math>L = \{a^n b^n \mid n \geq 0\}</math>

oder:

<math>L = \{ww \mid w \in \{0,1\}^*\}</math>

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 ==

{| class="wikitable"
! 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]]

== Kategorien ==

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Automatentheorie]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:Berechenbarkeit]]
[[Kategorie:Informatik]]

Automatentheorie - Versionsgeschichte