Grenzen endlicher Automaten

Ein endliches Gedächtnis

Ein DEA hat keinen Notizzettel: Alles, was er über die schon gelesenen Zeichen weiß, steckt in seinem aktuellen Zustand.

Gedächtnis:nur der aktuelle Zustand — sonst speichert ein DEA nichts.
Vorgeschichte:das bisher gelesene Anfangsstück des Worts, z. B. aaa \(=a^3\).
Gleicher Zustand:zwei Vorgeschichten, die im selben Zustand enden, behandelt der DEA ab dann völlig gleich — bei jedem angehängten Rest.
Grenze:\(k\) Zustände \(\Rightarrow\) höchstens \(k\) Vorgeschichten lassen sich unterscheiden.
Beschränkt zählen:„höchstens drei a“ oder „Anzahl der a durch 3 teilbar“ — endlich viele Fälle, das schafft ein DEA.
Unbeschränkt zählen:„genauso viele b wie vorher a“ — unendlich viele Fälle, das schafft kein DEA.

Der Versuchsautomat soll \(L=\{a^n b^n\mid n\ge 0\}\) erkennen: a zählt einen Zustand hoch, b einen herunter, z0 ist Start- und Endzustand. Stelle \(k\) und \(n\) ein und beobachte die Zustandsfolge beim Lesen von \(a^n\). Gleiche Farbe heißt gleicher Zustand.

Zustände k

Länge n des a-Blocks

Halte fest: Sobald zwei Vorgeschichten \(a^i\) und \(a^j\) im selben Zustand enden, muss der Automat \(a^ib^i\) und \(a^jb^i\) gleich behandeln — eines davon falsch. Mehr Zustände schieben das Problem nur hinaus: Bei \(n=k\) ist es immer da.

Was ein DEA nicht kann

Mit der Idee aus dem Applet lässt sich zeigen, dass es für \(L=\{a^n b^n\mid n\ge 0\}\) überhaupt keinen DEA gibt — ganz gleich, wie viele Zustände er hat.

Herleitung:

\(\text{DEA } A \text{ mit } \textcolor{#2c5fb5}{k} \text{ Zuständen erkennt } L\)

Annahme

Wir nehmen das Gegenteil der Behauptung an und führen es zum Widerspruch.

\(a^0,\ a^1,\ a^2,\ \dots,\ a^{k}\)

Schubfach

Das sind \(k+1\) Vorgeschichten, aber nur \(\textcolor{#2c5fb5}{k}\) Zustände — mindestens zwei landen im selben Zustand.

\(a^{\textcolor{#4a7530}{i}} \text{ und } a^{\textcolor{#e2574c}{j}} \ \longrightarrow\ \text{Zustand } z,\quad i<j\)

gleicher Zustand

Nach dem Lesen von \(a^i\) und von \(a^j\) steht \(A\) im selben Zustand \(z\).

\(a^{\textcolor{#4a7530}{i}}\,\textcolor{#7c5fb5}{b^i} \text{ und } a^{\textcolor{#e2574c}{j}}\,\textcolor{#7c5fb5}{b^i}\)

\(b^i\) anhängen

Ab \(z\) liest \(A\) in beiden Fällen dieselben Zeichen und durchläuft dieselben Zustände.

\(A \text{ akzeptiert } a^ib^i \iff A \text{ akzeptiert } a^jb^i\)

gleiches Urteil

Beide Wörter enden im selben Zustand — entweder beide angenommen oder beide abgelehnt.

\(a^ib^i\in L,\quad a^jb^i\notin L\) ↯

Widerspruch

Wegen \(i\ne j\) gehört nur eines der Wörter zu \(L\). Die Annahme ist falsch: Kein DEA erkennt \(L\).

Reguläre Sprache:eine Sprache, die ein DEA erkennt.
Klammerung:korrekt geklammerte Ausdrücke wie (()()) — wie bei \(a^nb^n\) müsste man beliebig viele offene Klammern mitzählen: nicht regulär.
Palindrome:Wörter wie abba oder aabaa — die ganze erste Hälfte müsste gespeichert werden: nicht regulär.
Beschränkte Tiefe:Klammern mit Tiefe höchstens 2 (oder 10) — endlich viele Tiefen, je Tiefe ein Zustand: regulär.

Klammerung mit Tiefe höchstens 2: drei Zustände genügen

Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF. Der Zustand merkt sich die aktuelle Tiefe 0, 1 oder 2.

Merke

Grenze eines DEA: Ein DEA mit \(k\) Zuständen unterscheidet höchstens \(k\) Vorgeschichten. Darum erkennt kein DEA die Sprache \(L=\{a^n b^n\mid n\ge 0\}\) — unbeschränktes Zählen ist unmöglich.

Allgemeine Hinweise

Mehr Zustände helfen nicht

Auch ein DEA mit 1000 Zuständen scheitert — spätestens bei \(a^{1000}\) wiederholt sich ein Zustand. Das Argument gilt für jedes \(k\).

Erst a, dann b geht

„Erst nur a, dann nur b“ ohne gleiche Anzahl ist regulär. Unmöglich wird es erst durch das Vergleichen zweier unbeschränkter Anzahlen.

Endliche Sprachen gehen immer

Ist \(n\) nach oben begrenzt, etwa \(n\le 5\), ist die Sprache endlich — dann gibt es einen DEA, der einfach bis 5 mitzählt. Die Grenze betrifft nur unbeschränkte Anzahlen.