Mindestanzahl von Zuständen in einer DFA mit '1' als 5. Symbol von rechts

Question

Was ist die Mindestanzahl von Zuständen, die in einer DFA benötigt werden, um die Saiten mit '1' als 5. Symbol von Recht zu akzeptieren? Saiten werden über dem Alphabet {0,1} definiert.

Answer 1

Das Myhill-Nerode-Theorem ist ein nützliches Instrument zur Lösung dieser Art von Problemen.

Die Idee ist, eine Reihe von Äquivalenzklassen von Strings aufzubauen, wobei die Idee der "Unterscheidung von Erweiterungen" verwendet wird. Betrachten Sie zwei Saiten x und y. Wenn es eine String z gibt, so dass genau eines von XZ und YZ in der Sprache ist, dann ist z eine Unterscheidungsverlängerung, und X und Y müssen zu verschiedenen Äquivalenzklassen gehören. Jede Äquivalenzklasse karten in einem anderen Zustand im minimalen DFA.

Für die Sprache, die Sie beschrieben haben, seien Sie x und y ein Paar verschiedener 5-Zeichen-Zeichenfolgen über {0,1}. Wenn sie sich an Position N unterscheiden (von rechts abzählen, ab 1), dann ist jeder String Z mit einer Länge 5-N eine Unterscheidungsverlängerung: Wenn X an Position N eine 0 hat und y eine 1 an Position N hat, hat Dann wird XZ abgelehnt und YZ akzeptiert. Dies gibt 2⁵ = 32 Äquivalenzklassen.

Wenn s eine Zeichenfolge mit Länge k <5 Zeichen ist, gehört sie zur gleichen Äquivalenzklasse wie 0^(5-k)S (dh 1 Padding links hinzufügen, bis es 5 Zeichen lang ist).

Wenn S eine Zeichenfolge mit Länge K> 5 Zeichen ist, wird seine Äquivalenzklasse durch die letzten 5 Zeichen bestimmt.

Daher fallen alle Zeichenfolgen über {0,1} in eine der oben beschriebenen 32 Äquivalenzklassen, und durch den Myhill-Nerode-Theorem hat der minimale DFA für diese Sprache 32 Zustände.