Nichtdeterministische Automaten

Keine Eindeutigkeit

Der folgende Automat zur Erkennung der Sprache LBin = {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.

JFlap - Grammatik

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.

JFlap - Nichdeterminischer Automat

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 - Nichtdeterminischer Automat

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:

JFlap - Nichtdeterminischer Automat

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.

JFlap - Determinischer Automat

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

JFlap - Nichdeterminischer Automat

Aufgabe 2

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

X

Fehler melden

X

Suche