Nichtdeterministische Automaten

Keine Eindeutigkeit

Der folgende Automat zur Erkennung der Sprache L_Bin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}

ist nichtdeterminstisch in dem Sinne, dass er zulässt, dass von einem Zustand bei derselben Eingabe Übergänge in unterschiedliche Folgezustände möglich sind.

Zudem enthält der Automat Zustandsübergänge ohne Eingaben (sog. λ-Übergänge).

Spracherkennung mit nichtdeterministischen Automaten

Spracherkennung mit nichtdeterministischen Automaten funktioniert so ähnlich wie Spracherkennung mit deterministischen Automaten.

Wenn man in JFlap die Menupunkte [Input][Step by State] auswählt und beispielsweise das Wort 1001 eingibt, dann lässt sich die nichtdeterministische Verarbeitung des Eingabeworts anschließend mit [Step] Schritt für Schritt aktivieren. Nach zwei Schritten ergibt sich folgende Situation:

JFlap spielt alle möglichen Zustandsübergänge für das vorgegebene Eingabewort durch und zeigt an, welche Zustände dabei erreicht werden können. Nach mehreren Schritten erreicht man folgende Situation:

Aufgabe 1

Probiere das selbst einmal aus. Woran erkennt man, ob ein Wort (nicht) akzeptiert wird?

Zusammenhang zwischen deterministischen und nichtdeterministischen Automaten

JFlap bietet die Möglichkeit an, aus einem nichtdeterministischen Automaten einen deterministischen Automaten zu konstruieren.

Hierzu muss man die Menupunkte [Convert][Convert to DFA] auswählen und den Automaten dann schrittweise generieren.

Aufgabe 2

Probiere das selbst einmal aus. Welches Konzept ist mächtiger - das Konzept deterministischer Automat oder das Konzept nichtdeterministischer Automat?