Myhill/ Nerode

Eine Sprache ist genau dann regulär, wenn der Index R[L] endlich ist.

Wenn man eine Äquivalenzrelation (R[L]) findet, die die Sprache in endlich viele (Äquivalenz-)Restklassen zerlegt, so ist die Sprache regulär.

Am einfachsten ist vielleicht die Erklärung über den Automaten:

(S.42): "Es gilt x R[L] y genau dann, wenn für alle Wörter z e Sigma* gilt: xz e L <=> yz e L     "

Wenn sie sich alle gleich verhalten - soll heissen, wenn sie durch Anhängen (oder auch Voranschreiben/ Dazwischenschreiben etc.) von einer bestimmten Zeichenfolge allesamt wieder in derselben Restklasse landen.

Das ist genau wie bei Modulo auf Zahlen.
Betrachten wir dort z.B. die Äquivalenzrelation "mod 2", dann erhalten wir genau zwei Restklassen (Äquivalenzklassen), nämlich die geraden
[2n]={2n | n e N}
und die ungeraden Zahlen
[2n+1]={2n+1 | n e N}

Der (Minimal-/ Äquivalenz-) Automat (->S.45) hat gerade so viele Zustände, wie es Äquivalenzklasen gibt.
Die von den jeweiligen Klassen (Zuständen) ausgehenden Pfeile beschreiben gerade, wo alle Wörter in der Äquivalenzklasse unter der Eingabe "hingehen".

Wenn man nun also endlich viele Äquivalenzklassen gefunden hat, kann man den zugehörigen Automat angeben und da der endlich ist, hat man gezeigt, dass die Sprache regulär ist.

Da in der Formulierung "genau dann, wenn" steht, ist er eine äquivalente Definition der Typ 3 (regulären) Sprachen (im Ggs. zum Pumping Lemma).

Wenn man nun also zeigt, dass es endlich viele Restklassen gibt, hat man die Regularität der Sprache gezeigt.
Die Äquivalenzklassen bilden dabei eine Partition von Sigma*:
Das heisst jedes erdenkliche Wort in Sigma* liegt genau in einer Äquivalenzklasse.
Die Vereinigung aller Klassen bildet also Sigma*.

Ebenso natürlich, wenn man die Existenz unendlich vieler Äquivalenzklassen zeigt, die Nichtregularität.
Dabei muss man zeigen, dass die gefundenen Äquivalenzklassen auch alle paarweise verschieden sind (also nicht zusammengefasst werden können).

(-> Blatt 5 Aufgabe 3+4)

Das ist von Aufgabe zu Aufgabe verschieden.
Man muss sich überlegen, was für die Wörter charakteristisch ist, also z.B.
"Welche Art von Wörtern wird akzeptiert?"
"Welche nicht?"
"Warum nicht?"
Alle Klassen zusammen müssen ganz Sigma* ergeben.


- - Am Beispiel von Blatt 5 Aufgabe 3 sieht das Vorgehen so aus: - -
Was wird erkannt?
"0y10" "0y11"
Also gut, dann werden das wohl schon mal zwei Restklassen sein:
[0y10]={0y10 | y e Sigma*}
[0y11]={0y11 | y e Sigma*}
"Egal, was man zwischendrin einfügt, gelangt man immer an die gleiche Stelle im Automat..."

Alle Restklassen zusammen müssen ganz Sigma* ergeben, was kann es noch geben?
Das leere Wort.
Wörter, die mit 1 beginnen.
Wörter, die zwar mit 0 beginnen, aber auf 01 oder 00 enden.
Dann haben wir ganz Sigma* partitioniert.

Es ergeben sich also folgende weiteren Restklassen:
[Epsilon] = {Das leere Wort}
[1y] = {1y | y e Sigma*}
[0y01] = {0y01 | y e Sigma*}
[0y00] = {0y00 | y e Sigma*}

- Warum sind das alles verschiedene Äquivalenzklassen und nicht eine und warum ist die Aufteilung gerade so?
Das liegt daran, dass sich eben alle Wörter in einer Äquivalenzklasse gleich verhalten müssen:
"Egal welchen Repräsentanten ich aus der Klasse nehme, mit jedem anderen wäre es genau so gelaufen..."

Betrachten wir beispielsweise die beiden akzeptierenden Klassen [0y10] und [0y11]:
Hängen wir jeweils eine 0 an, so landen wir mit [0y10]0 in [0y00]; mit [0y11]0 in [0y10].
Damit können diese Äquivalenzklassen nicht zusammengefasst werden.
(Für den vollständigen Beweis der paarweisen Verschiedenartigkeit müsste man dies für alle Klassen unter allen Eingaben zeigen...)

© marc-oliver pahl