Satz von Rabin & Scott

Jede von einem NEA akzeptierte Sprache ist auch von einem DEA akzeptierbar.

Formale Darstellung

Sei ein NEA. Dann existiert ein DEA mit

• Potenzmenge von
• mit
• (Interpretation als kombinierter Einzelzustand!)

der die gleiche Sprache wie akzeptiert, also

Grundidee

• Alle möglichen Zustandsmengen als einen Zustand auffassen
• Transitionen zwischen Zustandsmengen angeben
• Neue Endzustände: Menge enthält mindestens einen alten Endzustand

Beispiel

NEA: oder endet auf

Äquivalenter DEA:

Ausführlich

• Vom Einfingerzustand aus gibt es zwei Möglichkeiten: Zum einen können wir übergehen in wieder , zum anderen können wir übergehen in . Deswegen “teilen” wir unseren Finger auf, also setzen einen Finger auf und einen auf . Als Resultat landen wir im Zweifingerzustand .
• Wir können auf und auf anfangen, deswegen wird der Startzustand im DEA der Zweifingerzustand .
• Vom Zweifingerzustand gibt es beim Lesen von keine Möglichkeit von weiter zu gehen, deswegen fällt dieser Finger weg. Die einzige Möglichkeit ist von wieder in . Deswegen landen wir dann im Einfingerzustand .
• Vom Zweifingerzustand gibt es beim Lesen von gleich mehrere Möglichkeiten: Zum einen geht in über. Außerdem gibt es von zwei Möglichkeiten: Einmal wieder in und einmal in . Hier “teilt” sich also ein Finger und wird zu zwei. Als Resultat landen wir im Dreifingerzustand . Da im NEA ein Endzustand ist, ist dieser Zustand im DEA auch ein Endzustand.
• Vom Dreifingerzustand gibt es beim Lesen von keine Möglichkeiten mehr von oder von weiter zu machen, deshalb fallen diese Finger weg. Von geht es aber wieder in . Deswegen landen wir wieder im Einfingerzustand .
• Vom Dreifingerzustand gibt es beim Lesen von wieder mehrere Möglichkeiten: geht wieder über in , der Finger bei teilt sich wieder in und . Bei gibt es keine Möglichkeit mehr, deswegen fällt dieser Finger weg. Als Resultat landen wir wieder im selben Dreifingerzustand .