Akaibel: 1 Version importiert

2026-10-27T17:44:47Z

1 Version importiert

← Nächstältere Version	Version vom 27. Oktober 2026, 17:44 Uhr
(kein Unterschied)

sibiwikialt>Akaibel: /* Beziehung zu deterministischen endlichen Automaten */

2023-11-09T19:41:09Z

Beziehung zu deterministischen endlichen Automaten

Neue Seite

[[Kategorie:endliche Automaten]]
[[Kategorie:Informatik-Q2]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik]]

Nichtdeterministische endliche Automaten unterscheiden sich von [[Deterministischer Endlicher Automat|Deterministischen endlichen Automaten]] in zwei wesentlichen Punkten:
* '''Die Übergänge zwischen den Zuständen sind nicht eindeutig.''' D.h. es kann für ein Symbol und einen Zustand mehrere mögliche Übergänge geben.
* '''Ein Wort gilt als akzeptiert, wenn es für das Wort einen Übergang vom Anfangs- in einen Endzustand gibt.''' D.h.: Nicht jeder "Weg" muss zu einem Endzustand führen - es reicht, wenn es einen Weg gibt! ''Und der "richtige" Weg ist manchmal ziemlich schwer zu finden...''

=Fachbegriffe=
Nicht-Deterministischer endlicher Automat (NEA), Zustand, Anfangszustand, Endzustände, Alphabet, Übergang, Zustandsübergangsfunktion, Übergangsgraph, prüfen, "es gibt einen Weg"

=Beispiel=

[[File:Automat007nichtDeterministisch.png|thumb|Der KGB-Automat als Nicht-deterministischer endlicher Automat. |557px]]

Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.

Man sieht, dass im Zustand <code>q0</code> der Übergang für die 0 nicht eindeutig ist; man kann entweder bei q0 bleiben oder zu q1 übergehen.

Die Darstellung als Nicht-deterministischer endlicher Automat ist oft viel einfacher als die Darstellung als [[Deterministischer Endlicher Automat]].

=Beziehung zu deterministischen endlichen Automaten=
* Jeder deterministische endliche Automat ist (ohne irgendwelches Dazutun) direkt auch ein Nicht-deterministischer endlicher Automat.
* Zu jedem Nicht-deterministischen endlichen Automaten kann man eine deterministischen endlichen Automaten konstruieren.
** Das Verfahren dazu heißt '''[[Potenzmengenkonstruktion]]''' und ist reichlich kompliziert, funktioniert aber immer! (Das ist mathematisch bewiesen...)

=Zustandsfolgen für NEAs=
Wenn prüfen will, ob ein Wort von einem NEA erkannt wird, dann muss man jede der (nicht deterministischen) Möglichkeiten durchprüfen! Das gilt vor allem, wenn man zeigen will, dass ein Wort '''nicht''' akzeptiert wird. 
'''Beispiel: Das Wort 70008: Prüfung mit Zustandsfolgen'''
<code>
'''7 0 0 0 8'''
q0 -> q0 -> q0 -> q0 -> q0 -> q0 kein Endzustand erreicht.
q0 -> q0 -> q0 -> q0 -> q1 -> Senke
q0 -> q0 -> q0 -> q1 -> q2 -> Senke
q0 -> q0 -> q1 -> q2 -> Senke

Damit ist gezeigt, dass "70008" nicht akzeptiert wird.
</code>
Man sieht - das ist sehr aufwändig - und das umso mehr, je komplizierter der Automat wird.

Bei diesem Automat kann man natürlich durch logische Überlegungen schnell ermitteln, dass "70008" nicht akzeptiert wird, aber das geht ja nicht immer. Deswegen lohnt es sich, eine '''nicht-deterministische Zustandsfolge''' zur Überprüfung von Wörtern zu nutzen!

== Nicht-deterministische Zustandsfolgen ==
Bei einer nicht-deterministischen Zustandsfolge schreibt man nach jedem Zeichen '''alle möglichen Zustände''' auf. 
'''Beispiel: Das Wort 70008 - Prüfung mit einer nicht-deterministischen Zustandsfolge'''
<code>
'''7 0 0 0 8'''
q0 -> {q0} -> {q0,q1} -> {q0,q1,q2} -> {q0,q1,q2} -> {q0}
</code>
Die Menge nach der Abarbeitung des Wortes "70008" enthält nur den Zustand q0. 
Das heißt: Es gibt keinen Weg zu einem Endzustand, und damit ist das Wort nicht akzeptiert.

=Beziehung zu regulären Grammatiken=
[[Datei:DEA-RG-NEA-reg-Sprache.png|400px|thumb|right|Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache]]
* '''Zu jedem nicht-deterministischen endlichen Automaten lässt sich einfach eine [[Reguläre Grammatik|reguläre Grammatik]] konstruieren:'''
** Aus jedem Zustand des Automaten macht man ein Nicht-Terminal in der Grammatik - und der Rest ergibt sich von selbst.
* '''Zu jeder [[Reguläre Grammatik|regulären Grammatik]] lässt sich einfach ein nicht-deterministischer endlicher Automat konstruieren:'''
** Aus jedem Nichtterminalsymbol wird einen Zustand des Automaten gemacht und aus jeder Produktionsregel einen Übergang des Automaten.
** Der Nicht-deterministische endliche Automat ist deswegen ein Zwischenschritt beim Übergang von der [[Reguläre Grammatik|regulären Grammatik]] zum [[Deterministischer Endlicher Automat|deterministischen endlichen Automaten]].

Nicht-deterministischer endlicher Automaten - Versionsgeschichte

Akaibel: 1 Version importiert

sibiwikialt>Akaibel: /* Beziehung zu deterministischen endlichen Automaten */