1.4 NEA mit ɛ-Übergängen
Es gibt eine weitere Erleichterung beim Konstruieren von endlichen Automaten. Nämlich erlauben \(ɛ\)-Übergänge spontanes Wechseln von Übergängen, ohne dass eine Eingabe gelesen wird. Dies hilft insbesondere, wenn man versucht mehrere Optionen mit einem einzigen EA zu modellieren. Im Abschnitt 2.3.1 lernen wir einen weiteren grossen Vorteil von \(ɛ\)-Übergänge kennen. “\(ɛ\)” ist das Symbol für “keine Eingabe” und heisst “das leere Wort“. Das bedeutet, dass die Wörter \(abbb\), \(abbɛb\), \(aɛbbb\) und \(abɛbɛb\) alle dasselbe bedeuten.
Beispiel EA mit \(ɛ\)-Übergängen
Der folgende EA akzeptiert alle Wörter, welche aus den Buchstaben \(a\) und \(b\) bestehen, wobei das Wort entweder auf \(aa\) endet oder irgendwo \(bb\) vorkommt.
Definition: nichtdeterministischer endlicher Automat mit \(ɛ\)-Übergängen (\(ɛ\)-NEA)
Ein nichtdeterministischer endlicher Automat mit \(ɛ\)-Übergängen (\(ɛ\)-NEA) ist ein 5-Tupel \(M = (Q, Σ, \delta, q_0, F)\) wobei \( Q, Σ, q_0\) und \( F\) wie beim DEA definiert sind und die Übergangsfunktion \(δ \) definiert ist als
\(δ : Q×(Σ \cup \{ɛ\}) → P(Q)\).
Beispiel \(ɛ\)-NEA für Dezimalzahlen
Praktisch sind \(ɛ\)-NEA beispielsweise beim entwerfen eines EA, welcher Dezimalzahlen akzeptiert. Wir entwerfen also einen EA, der in einem akzeptierenden Zustand landet, sobald das Wort eine Dezimalzahl war. D.h.
- optionales + oder – sind erlaubt (ausser vor der Zahl 0. Dort soll kein Vorzeichen stehen.)
- Zeichenreihe von Ziffern mit optionalem Dezimalpunkt dazwischen sind erlaubt.
- unnötige 0 sollen nicht akzeptiert werden. Z. B. ist 007 keine Dezimalzahl, aber z. B. 0.00 schon.
Äquivalenz von DEA und \(ɛ\)-NEA (und NEA)
Ein DEA ist ein Spezialfall eines NEA. Ein NEA ist wiederum ein Spezialfall eines \(ɛ\)-NEA. (Die Übergänge eines \(ɛ\)-NEA’s müssen nicht \(ɛ\)-Übergänge benutzen, dürfen dies aber.) Etwas überraschender ist, dass man jeden \(ɛ\)-NEA in einen NEA und diesen wiederum in einen DEA umwandeln kann. Dies geschieht ebenfalls mittels einer geschickten Teilmengenkonstruktion, welche die \(ɛ\)-Übergänge beachtet. Wir werden diese Äquivalenz nicht genauer begründen.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 1_4_E_NEA_Notizen.