Satz von Myhill-Nerode

Der Satz von Myhill-Nerode gibt im Fachgebiet Formale Sprachen der Theoretischen Informatik ein notwendiges und hinreichendes Kriterium dafür an, dass eine Formale Sprache regulär ist. Er wurde im Jahr 1957/1958 von John Myhill und Anil Nerode vorgestellt und bewiesen.

Umgangssprachlich ausgedrückt dient der Satz hauptsächlich dazu, herauszufinden, ob eine Formale Sprache so „gutartig“ oder „einfach gestrickt“ ist, dass ein Computer mit endlich begrenztem Speicher automatisch feststellen kann, ob eine Zeichenfolge ein Wort der Sprache ist oder nicht.

Satz

Hinweis: Die nachfolgenden Fachbegriffe werden im Artikel Formale Sprache erläutert.

Gegeben sei eine Formale Sprache L über dem Alphabet Σ sowie die zugehörige Nerode-Relation ~. Der Satz von Myhill-Nerode lautet:

Es existiert genau dann ein deterministischer endlicher Automat, der L akzeptiert, wenn der Index der zugehörigen Nerode-Relation endlich ist.

Formal:

$\exists A:\ L(A)=L\qquad \Longleftrightarrow \qquad |\Sigma ^{*}/\sim |<\infty$

wobei A ein Deterministischer endlicher Automat ist und L(A) die Sprache, die er akzeptiert.

Anwendung

Die Existenz eines deteministischen endlichen Automaten, der L akzeptiert, ist notwendiges und hinreichendes Kriterium dafür, dass L eine reguläre Sprache ist. Die Logische Äquivalenz des Satzes ermöglicht es also sowohl zu zeigen, dass eine formale Sprache regulär ist, als auch zu zeigen, dass sie es nicht ist. Da dies die wichtigste Anwendung des Satzes von Myhill-Nerode ist, wird er vielfach auch so gelesen:

Die Sprache L ist genau dann regulär, wenn der Index der zugehörigen Nerode-Relation endlich ist.

Weiter lässt sich folgern, dass die Anzahl der Zustände eines minimalen endlichen deterministischen Automats, der L akzeptiert, dem Index der zugehörigen Nerode-Relation entspricht.

Beispiele

Alle Sprachen mit endlich vielen Wörtern endlicher Länge sind regulär

Die Sprache L über dem Alphabet Σ enthalte endlich viele Wörter und alle Wörter aus L haben endliche Länge. Das heißt es existieren natürliche Zahlen m und n, so dass gilt:

• $|L|\leq m$
• $|w|\leq n\quad \forall w\in L$.

Da zu jedem Wort soviele Präfixe existieren, wie es Buchstaben enthält, und das leere Wort ε auch als Präfix zählt, hat die Sprache L insgesamt höchstens n·m+1 Präfixe und ebensoviele Äquivalenzklassen. Es gilt also:

$ind(L)\leq n\cdot m+1<\infty$.

Das heißt die Anzahl der Äquivalenzklassen ist endlich und aus dem Satz von Myhill-Nerode folgt, dass die Sprache L regulär ist. Man kann also verallgemeinernd sagen: Jede Sprache, die endlich viele Wörter enthält, die jeweils endliche Länge besitzen, ist regulär.

Die Sprache L := {a, aa, aaa, ...} ist regulär

Ein minimaler Deterministischer endlicher Automat, der die Sprache a* akzeptiert.

Die Sprache L über dem Alphabet Σ := {a} sei definiert durch:

$L:=\{a^{\star }\}$.

Es ergibt sich genau eine Äquivalenzklasse bezüglich der Nerode-Relation, nämlich L selbst:

$[\epsilon ]=[a]=[aa]=[aaa]=\ldots =\{\epsilon ,a,aa,aaa,\ldots \}=\{a^{\star }\}=L$.

Das heißt alle Präfixe der Sprache L lassen sich mit denselben Suffixen zu Wörtern aus L ergänzen. Damit ist der Index der Nerode-Relation endlich:

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle ind(L) = 1 < \infty} .

Aus dem Satz von Myhill-Nerode folgt schließlich, dass die Sprache L regulär ist.

Die Sprache L := {ab, aabb, aaabbb, ...} ist nicht regulär

Ausschnitt eines nicht-endlichen, deterministischen Automaten, der die Formale Sprache L akzeptiert. Jedes der unendlich vielen Wörter aus L benötigt einen eigenen Endzustand, der Automat hat also unendliche Größe.

Die Sprache L über dem Alphabet Σ := {a, b} sei definiert durch:

$L:=\{a^{n}b^{n}|n\in \mathbb {N} \}$.

Es ergeben sich insbesondere folgende Äquivalenzklassen bezüglich der Nerode-Relation:

${\begin{matrix}&[a]&=&\{a,aab,aaabb,\ldots \}&\mathrm {Suffix:} &\{b\}\\&[aa]&=&\{aa,aaab,aaaabb,\ldots \}&\mathrm {Suffix:} &\{bb\}\\&[aaa]&=&\{aaa,aaaab,aaaaabb,\ldots \}&\mathrm {Suffix:} &\{bbb\}\\&\vdots &&\vdots \\&[a^{k}]&=&\{a^{i}b^{i-k}|k\leq i\in \mathbb {N} \}&\mathrm {Suffix:} &\{b^{k}\}\\&\vdots &&\vdots \end{matrix}}$

Diese Äquivalenzklassen sind paarweise verschieden, das heißt es gilt:

$[a^{i}]\neq [a^{j}]\quad \forall i,j\in \mathbb {N} _{0}:i\neq j$.

Daraus folgt, dass bereits die Anzahl dieser Äquivalenzklassen unendlich ist und – da die Anzahl aller Äquivalenzklassen von L nochmals größer ist – damit auch der Index der Nerode-Relation bezüglich L unendlich ist. Aus dem Satz von Myhill-Nerode folgt schließlich, dass die Sprache L nicht regulär ist.

Quellen

[1] - A. Nerode: Linear automaton transformations. Proceedings of the American Mathematical Society 9 (1958) pp. 541-544. - Nicht eingesehen.
[2] - J. Myhill: Finite automata and the representation of events. WADD TR-57-624 (1957), pp. 112-137 - Nicht eingesehen.
[3] U. Schöning: Theoretische Informatik - kurzgefasst, 4. Auflage, S. 42 ff

Weblinks

• Webseiten von Anil Nerode