Satz von Myhill-Nerode

mathematischer Satz

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 konstantem Speicher (d. h. mit endlich begrenztem Speicher, dessen Größe nicht von der Eingabe abhängt) automatisch feststellen kann, ob eine Zeichenfolge ein Wort der Sprache ist oder nicht.

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

Gegeben sei eine formale Sprache   über dem Alphabet   sowie die zugehörige Nerode-Relation  . Dann gilt:

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

Formal:

 

wobei   ein deterministischer endlicher Automat ist und   die Sprache, die er akzeptiert.

Anwendung

Bearbeiten

Die Existenz eines deterministischen endlichen Automaten, der   akzeptiert, ist notwendiges und hinreichendes Kriterium dafür, dass   eine reguläre Sprache ist. Der Satz kann also sowohl dazu verwendet werden zu zeigen, dass eine formale Sprache regulär ist, als auch um 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   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 deterministischen endlichen Automaten, der   akzeptiert, dem Index der zugehörigen Nerode-Relation entspricht.

Genauer gesagt: Sei   ein Repräsentantensystem von  , dann ist   der (eindeutige) minimale, deterministische Automat, der   akzeptiert, wobei

  •   Die Zustände entsprechen den Äquivalenzklassen nach  
  •   Der Startzustand entspricht der Äquivalenzklasse, in der das leere Wort liegt
  •   Endzustände entsprechen den Äquivalenzklassen der Wörter, die in   liegen (umgekehrt zerfällt   genau in die Äquivalenzklassen, die in   liegen, also  )
  •   für alle  

Dieser Zusammenhang gilt auch für nicht-reguläre Sprachen. Dort wird   eben nicht endlich, womit (aufgrund der Minimalität von  ) dann auch kein DEA für   existiert.

Eine weitere Anwendung besteht darin, dass mit Hilfe des Satzes bewiesen werden kann, dass (unabhängig vom P-NP-Problem) kein Polynomialzeit-Algorithmus existiert, der aus einem NEA einen äquivalenten DEA konstruiert. Es existieren Sprachen, die von einem NEA mit   Zuständen erkannt werden, die aber   Myhill-Nerode Äquivalenzklassen haben.

Ein Beispiel hierfür ist die Sprache   Sind   zwei unterschiedliche Wörter aus   der Länge  , dann unterscheiden sie sich an einer Position  . Somit liegt genau eines der Wörter   und   in   und es gilt  .

Die Ausgabe kann also exponentiell größer sein als die Eingabe und somit kann keine Turingmaschine die Ausgabe in weniger als Exponentialzeit berechnen. Für dieses Problem existiert damit kein wesentlich besserer Algorithmus als die Potenzmengenkonstruktion.

Beispiele

Bearbeiten

Endliche Sprachen sind regulär

Bearbeiten

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

  •  
  •  .

Da zu jedem Wort so viele Präfixe existieren, wie es Buchstaben enthält, und das leere Wort   auch als Präfix zählt, hat die Sprache   insgesamt höchstens   Präfixe und ebenso viele Äquivalenzklassen. Es gilt also:

 .

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

Die Sprache {ε, a, aa, aaa, …} ist regulär

Bearbeiten
 
Ein minimaler deterministischer endlicher Automat, der die Sprache   akzeptiert.

Die Sprache   über dem Alphabet   sei definiert durch:

 .

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

 .

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

 .

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

Die Sprache {ab, aabb, aaabbb, …} ist nicht regulär

Bearbeiten
 
Ausschnitt eines nicht-endlichen, deterministischen Automaten, der die Formale Sprache L akzeptiert. Jedes der unendlich vielen Wörter aus L benötigt einen eigenen Pfad zum Endzustand, der Automat müsste also unendlich groß sein.

Die Sprache   über dem Alphabet   sei definiert durch:

 .

Es ergeben sich insbesondere folgende Äquivalenzklassen bezüglich der Nerode-Relation (jedes Präfix eines Wortes dieser Sprache lässt nur ein Suffix zur Vervollständigung zu):

 

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

 .

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

Bemerkung

Bearbeiten

Es ist nicht erforderlich, die Klassenstruktur der einer Sprache   zugeordneten Äquivalenzrelation vollständig aufzuklären, um die Nicht-Regularität dieser Sprache zu zeigen. Andernfalls müssten noch weitere Äquivalenzklassen aufgestellt werden, um der Forderung von Äquivalenzrelationen gerecht zu werden, eine bestimmte Grundmenge (hier:  , also alle Wörter über dem Eingabealphabet  ) vollständig in disjunkte Äquivalenzklassen aufzuteilen.

Die Suffixe

Bearbeiten

Prinzipiell kann als Suffix jedes Wort über dem Eingabealphabet   eingesetzt werden, also z. B.   usw. Hier wurde für jede Äquivalenzklasse nur das jeweils einzige Suffix angegeben, für welches bei dessen Anfügung an die Elemente der jeweiligen Klasse alle auf diese Art entstandenen Wörter zu der Sprache   gehören. Für jedes andere Suffix würden alle entstandenen Wörter nicht zur Sprache   gehören. Darauf beruht die Nerode-Relation.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • Uwe Schöning: Theoretische Informatik – kurzgefasst. 5. Auflage. Spektrum, Heidelberg 2008, ISBN 978-3-8274-1824-1, (HochschulTaschenbuch), S. 34–38.
  • A. Nerode: Linear automaton transformations. In: Proceedings of the American Mathematical Society 9, 1958, ISSN 0002-9939, S. 541–544.
  • J. Myhill: Finite automata and the representation of events. In: WADD TR 57-624, 1957, ZDB-ID 2518731-4, S. 112–137.