5.6 Die Grenzen regulärer Sprachen

Noch spannender, als zu erkunden, was möglich ist, ist aus Sicht eines theoretischen Informatikers, zu erkunden, was nicht möglich ist. Also Grenzen aufzuzeigen. Wir haben in den letzten vier Teilkapiteln gezeigt, was man mit regulären Sprachen und endlichen Automaten alles beschreiben kann. Nun wollen wir die Grenzen regulärer Sprachen verstehen, also das, was sie nicht mehr beschreiben können.

Beispiel 5.6.1 Sei

L

die Sprache aller Wörter über dem Alphabet

Σ = {a, b}

, die die Form

a^{n} b^{n}

haben; also eine beliebig lange Folge von

a

s, gefolgt von genau so vielen

b

s. Hier ist eine kontextfreie Grammatik für

L

\begin{aligned} S & \to ϵ \\ S & \to a S b \end{aligned}

Können wir eine reguläre Grammatik für $L$ schreiben? Irgendwie klingt das nicht plausibel. Reguläre Grammatiken können ja immer nur ein Wort von links nach rechts erzeugen; für $L$ scheint das irgendwie nicht zu reichen.

Übungsaufgabe 5.6.2 5.6.1 Versuchen Sie ein paar Minuten, eine reguläre Grammatik für

L

zu schreiben oder versuchen Sie, zu argumentieren, dass das nicht möglich ist.

Wir sind nun also recht überzeugt, dass $L$ nicht regulär ist. Nur, wie können wir das formal beweisen? Vielleicht könnten wir annehmen, dass es eine reguläre Grammatik $G = ({a, b}, N, P, S)$ gibt und dann argumentieren, dass $G$ nicht richtig ist; zum Beispiel Produktionen danach einteilen, ob sie $X \to a Y$ oder $X \to b Y$ machen, und dann die darin involvieren Nichtterminale $X$ und $Y$ weiter betrachten.

Zu Hilfe kommt uns die Tatsache, dass wir für reguläre Sprachen nun viele äquivalente Modelle gefunden haben:

Reguläre Grammatiken.
Erweitert reguläre Grammatiken, die also Produktionen wie $X \to a b Y$ erlauben.
Vereinfachte reguläre Grammatiken, in denen Produktionen wie $X \to a$ und $X \to Y$ nicht vorkommen; wo also die rechte Seite nie aus einem einzelnen Zeichen besteht.
Endliche Automaten.
Nichtdeterministische endliche Automaten.

Formal sind all diese Modelle gleich mächtig: wir können ein Modell in ein anderes umwandeln, ohne das die erzeugte bzw. akzeptierte Sprache sich ändern. Wenn wir nun zeigen wollen: $L$ ist nicht regulär, dann können wir das einfachste Modell nehmen und dagegen argumentieren. Nach meinem Darfürhalten sind endliche Automaten das einfachste der fünf aufgeführten Modelle. Also:

Angenommen, $L$ wäre regulär. Dann gäbe es auch einen endlichen Automaten $M = ({a, b}, Q, q_{0}, F, δ)$ , der $L$ akzeptiert. Wir müssen zeigen, dass das nicht sein kann. Also dem Automaten $M$ einen Fehler nachweisen. Ein endlicher Automat kann sich ja nur beschränkt viele Dinge "merken": er weiß nur, in welchem Zustand er gerade ist. Um Wörter der Form $a^{n} b^{n}$ zu erkennen, müsste er sich allerdings merken, wieviele $a$ 's er bereits gelesen hat. Vergisst er es, kann er bei den folgenden $b$ 's nicht mehr richtig mitzählen. Unser Plan ist also, das Gedächtnis des Automaten zu überfordern.

Setzen wir diesen Plan in die Tat um. Wir füttern dem Automaten eine Folge von $a a a a a a a . . .$ und beobachten die Zustandsfolge $q_{0}, q_{1}, q_{2}, \dots$ , die sich daraus ergibt. Formal: $\begin{array}{r} q_{i} := \hat{δ} (q_{0}, a^{i}), \end{array}$ wobei $a^{i}$ das Wort ist, dass aus $i$ vielen $a$ 's hintereinander besteht. Da der Automat nur $| Q |$ viele Zustände hat, muss sich nach mindestens $| Q |$ vielen $a$ 's eine Wiederholung einstellen, also $q_{i} = q_{j}$ für $0 \leq i < j \leq | Q |$ . Die Wörter $a^{i}$ und $a^{j}$ bringen also den Automaten beide in den Zustand $q_{i}$ ; der Automat kann also nicht unterscheiden, ob er gerade $i$ viele oder $j$ viele $a$ 's gelesen hat. Nun schlagen wir zu:

Wir füttern den Automaten mit dem Wort $a^{i} b^{i}$ . Der Automat landet in einem Zustand $q^{*}$ : $\begin{array}{r} q_{0} \overset{a^{i}}{\to} q_{i} \overset{b^{i}}{\to} q^{*} \end{array}$ Das Wort $a^{i} b^{i}$ ist in der Sprache $L$ . Dere Zustand $q^{*}$ muss also ein akzeptierender Zustand sein. Nun füttern wir ihn mit dem Wort $a^{j} b^{i}$ . Der Automat landet wo? $\begin{array}{r} q_{0} \overset{a^{j}}{\to} q_{i} \end{array}$ da ja $a^{i}$ und $a^{j}$ ihn in den selben Zustand bringen. Daraufhin geschieht abermals $q_{i} \overset{b^{i}}{\to} q^{*}$ , also insgesamt $\begin{array}{r} q_{0} \overset{a^{j}}{\to} q_{i} \overset{b^{i}}{\to} q^{*} \end{array}$ Wir haben aber bereits gesehen, dass $q^{*}$ ein akzeptierender Zustand sein muss; also akzeptiert der Automat auch $a^{j} b^{i}$ ; das ist aber ein Fehler, denn $a^{j} b^{i} \notin L$ . Der Automat ist also fehlerhaft. Da wir dieses Argument ganz allgemein für einen endlichen Automaten $M$ geführt haben, schließen wir:

Wenn

M

ein endlicher Automat ist, dann gilt

L (M) \neq L

. Daher ist

L

keine reguläre Sprache.

Zusammenfassend lautet unser Argument: wenn der Automat die Präfixe $α$ und $α^{'}$ nicht unterscheiden kann, dann kann er die Wörter $α β$ und $α^{'} β$ auch nicht unterscheiden; er muss also entweder beide akzeptieren oder beide ablehnen.

Das Argument, dass die Sprache ${a^{n} b^{n} | n \geq 0}$ nicht regulär ist, war nicht allzu schwer, fühlt sich aber etwas ad hoc an, also für diesen Fall maßgeschneidert. Es stellt sich aber heraus, dass man bei allen nicht-regulären Sprachen ein solches Argument anführen kann. Die Hauptarbeit besteht nun darin, Konzepte wie der Automat kann $α$ nicht von $α^{'}$ unterscheiden und der Automat muss aber $γ$ von $γ^{'}$ unterscheiden können zu formalisieren.

Definition 5.6.3 $M$ -Äquivalenz Sei

M = (Σ, Q, q_{s t a r t}, F, δ

ein (deterministischer) endlicher Automat. Zwei Wörter

α, β \in Σ^{*}

sind $M$ -äquivalent, geschrieben

\begin{array}{r} α \equiv_{M} β, \end{array}

wenn

\hat{δ} (q_{s t a r t}, α) = \hat{δ} (q_{s t a r t}, β)

gilt; wenn sie also den Automaten in den gleichen Zustand bringen.

Wir können bereits ein bisschen über $\equiv_{M}$ aussagen. Wenn beispielsweise $M$ ein endlicher Automat für die Sprache $L$ ist und $α \equiv_{M} β$ gilt, dann sind entweder beide Wörter in $L$ (nämlich wenn $\hat{δ} (q_{s t a r t}, α)$ ein akzeptierender Zustand ist) oder beide Wörter nicht in $L$ (falls es kein akzeptierender Zustand ist).

Auch sehen wir: wenn $α \equiv_{M} β$ , dann gilt $α γ \equiv_{M} β γ$ : $α$ und $β$ brigen den Automaten in den gleichen Zustand, und danach liest er in beiden Fällen das Wort $γ$ , endet also in beiden Fällen im gleichen Zustand.

Definition 5.6.4 -Äquivalenz Sei

eine Sprache. Zwei Wörter

sind -äquivalent, geschrieben

wenn für alle

die Wörter

und

entweder beide in

oder beide nicht in

sind.

Beobachtung 5.6.5 Sei

die vom endlichen Automaten

akzeptierte Sprache. Wenn

gilt, dann auch

Beweis. Nehmen wir an

; es gibt also einen Zustand

mit

Des weiteren sei

, also

also

Abhängig davon, ob

oder nicht, sind

und

entweder beide in oder beide nicht in . In anderen Worten:

Hier ist nun ein allgemeiner Angriffsplan, wie man zeigt, dass eine Sprache nicht regulär ist: wir finden eine unendliche Folge von Wörtern , die alle nicht -äquivalent sind. Wenn nun ein endlicher Automat mit Zustandsmenge ist, dann müssen sich unter Eingabewörter mindestens zwei äquivalente finden, da sie ja nicht alle den Automaten in einen anderen Zustand bringen. Der Automat kann also die Sprache nicht erkennen. Formaler:

Definition 5.6.6 Sei

. Der Index von ist die Anzahl von Äquivalenzklassen der Relation

, also die größtmögliche Anzahl gegenseitig nichtäquivalenter Wörter

; dies ist möglicherweise unendlich.

Beobachtung 5.6.7 Sei

ein endlicher Automat von

die von ihm akzeptierte Sprache. Dann ist der Index von

höchstens die Anzahl

von Zuständen. Im Umkehrschluss heißt das: wenn

unendlichen Index hat, dann gibt es keinen endlichen Automaten, der

akzeptiert;

ist demnach nicht regulär.

Beweis. Wenn der Index von

größer wäre als

, dann hieße das, dass wir

nicht

-äquivalente

finden können. Sei

der Zustand, in dem der Automat landet, wenn er das Eingabewort

abarbeitet. Die Zustände

können nicht alle verschieden sein; es gibt unter diesen Wörtern also

mit

. Das heißt aber, dass es ein

gibt mit

und

(oder umgekehrt). Da

die Sprache

akzeptiert, muss auch folgendes gelten:

was aber nicht sein kann, da

und daher auch

, also

gelten würde.

Beispiel 5.6.8 Die Sprache

ist nicht regulär.

In der Tat hat diese Sprache unendlichen Index. Die Wörter sind alle nicht -äquivalent. Für und könnten wir zum Beispiel wählen, um zu zeigen, dass und ist.

Beispiel 5.6.9 Sei

die Sprache aller Palindrome. Also der Wörter

mit

, wobei

das Wort

in umgekehrter Reihnfolge gelesen ist. Die Sprache

ist ein klassisches Beispiel einer kontextfreien Sprache:

Sie ist nicht regulär: die Wörter

sind alle nicht

-äquivalent, da

aber

ist.

Übungsaufgabe 5.6.2 Betrachten Sie die Sprache aller

, die gleich viele

's wie

's haben:

Zeigen Sie, dass diese Sprache nicht regulär ist.

Wie mächtig ist diese "Index-Methode"? Es stellt sich heraus, dass sie vollständig ist: wenn eine Sprache endlichen Index hat, dann ist sie auch regulär.

Theorem 5.6.10 Eine Sprache

ist genau dann regulär, wenn sie endlichen Index hat.

Beweis. Eine Richtung haben wir bereits weiter oben gezeigt: wenn es zu

einen endlichen Automaten mit Zustandsmenge

gibt, dann ist der Index von

höchstens

Für die andere Richtung nehmen wir an, dass der Index von endlich ist, sagen wir . Es gibt also , die alle paarweise nicht -äquivalent sind. Allerdings ist ist auch die größte solche Zahl; dies heißt, jedes weitere ist äquivalent zu einem dieser . In anderen Worten: wir können in Teilmengen partitionieren: so dass innerhalb eines alle Wörter äquivalent sind, und zwischen zwei verschiedenen alle nicht äquivalent sind: Die Menge von Mengen nennt man eine Partition oder Partitionierung von .

Beachten Sie: wenn und , dann gilt auch . (Überlegen Sie sich, warum!) Auch gilt für jedes : entweder sind alle Wörter in in der Sprache, also oder keines, also , welches das leere Wort enthält.

Wir bauen nun einen endlichen Automaten mit der Zustandsmenge . Für führen wir die Produktion ein, wenn es ein mit gibt. Sehen Sie nun: wenn wir ein anderes nehmen, dann gilt , also ist auch . In anderen Worten: es gibt nur eine Produktion der Form , d.h. die Produktionen sind in der Tat ein Funktion und der Automat ist determinisitsch. Als Anfangszustand wählen wir dasjenige , für das gilt. Akzeptierende Zustände sind diejenigen , für die gilt. Also: Der Automat erkennt die Sprache ; die Anzahl seiner Zustände ist gleich dem Index der Sprache .

Wir können den Index nicht nur verwenden, um zu argumentieren, dass eine Sprache nicht regulär ist, sondern auch, um zu zeigen, dass eine bestimmte Menge an Zuständen optimal ist.

Beispiel 5.6.11 Der nichtdeterministische endliche Automat

akzeptiert die Sprache

aller

, deren viertletzter Buchstabe eine 1 ist. Unsere Konstruktion, ihn deterministisch zu machen, würde 16 Zustände erzeugen. Ist dies optimal? Ja, ist es:

Behauptung 5.6.12 Die Sprache

hat Index 16. Alle Wörter in

sind nicht

-äquivalent.

Beweis. Seien

zwei verschiedene Wörter. Dann gibt es ein

mit

und

(oder umgekehrt). Sei

, also ein String bestehend aus

Nullen. Das viertletzte Zeichen von

ist 0, das viertletzte Zeichen von

ist 1; also gilt

, und somit

. Der Index ist also mindestens 16. Das er höchstens 16 ist, sehen wir, indem wir einen determinisitschen Automaten mit 16 Zuständen bauen.

Allgemeiner: sei die Sprache aller , deren -letztes Zeichen eine 1 ist. Dann gibt es für einen nichtdeterministischen endlichen Automaten mit Zuständen und einen determinisitschen mit Zuständen. Es gibt keinen determinisitschen Automaten mit weniger als Zuständen.