André Vratislavsky

Übungsgruppe vom 09.11.99

Nichtdeterministische endliche Automaten

Wir wollten beweisen, daß die  regulären Sprachen den dfa-Sprachen entsprechen, um zwei verschiedene Modelle für dasselbe Konzept zu haben.
Dazu wollten wir zuerst zeigen, daß jede reguläre Sprache auch dfa-Sprache ist (Satz 1.9 der Vorlesung). Dies geschah durch Induktion über die Anzahl der regulären Verknüpfungssymbole in einem regulären Ausdruck bzw. Konstruktion eines dfa's.
Der reguläre Ausdruck hat ein äußerstes Verknüpfungssymbol.
Induktionsanfang: Ein oder kein Verknüpfungssymbol, dfa dafür konstruieren.
Induktionsannahme: Es gibt dfa's für die verknüpften Teilausdrücke.
Induktionsschritt: Konstruktion eines dfa's für die Verknüpfung. Dafür ist ein nichtdeterministischer Epsilon-Übergang hilfreich.
Daher definierten wir den nfa.
Nichtdeterministische endliche Automaten (nfa) unterscheiden sich von den deterministischen in folgenden Punkten:
Für ein Eingabesymbol sind von einem Zustand aus im allgemeinen mehrere Folgezustände erreichbar. Der Automat "rät", "welchen Weg er einschlagen soll". Eine Eingabe wird akzeptiert, falls es einen "richtigen" Weg gibt, d.h. einen, der zu einem akzeptierenden Zustand führt. Eine Eingabe wird nicht akzeptiert, falls es überhaupt keinen Weg zu einem akzeptierenden Zustand gibt.
Von den akzeptierenden Zuständen aus führen keine Übergänge weg, alle Eingaben "die von dort aus noch weiter wollen", werden nicht akzeptiert, sofern es für sie keinen anderen akzeptierenden Weg gibt. (Nicht eingezeichnete Übergänge entsprechen im nfa einem Übergang zu einem nichtakzeptierenden Zustand, von dem für alle Symbole eine Schleife in sich selbst führt.)

Konstruktion eines dfa aus einem nfa

Ein dfa ist zugleich auch ein nfa.
Umgekehrt gilt das nicht, jedoch läßt sich jeder nfa in einen dfa umwandeln, wobei jedoch teilweise erheblich mehr Zustände benötigt werden.
Diese Erkenntnis wird oft in Beweisen verwendet, wo es oft leichter ist, einen nfa zu konstruieren. Die Existenz des äquivalenten dfa's folgt dann automatisch.

Konstruktionsvorschrift:

Die Zustände des neuen Automaten entsprechen allen Teilmengen der Zustandsmenge des alten. Von diesen Teilmengen werden aber meistens nicht alle gebraucht. Jetzt werden die Zustandüberführungsfunktionen eingezeichnet.
Beispiel:

Alle Zustände, die nicht vom Startzustand aus erreichbar sind, können gestrichen werden.
Akzeptierend sind alle Zustände, die die alten akzeptierenden Zustände enthalten, z.B. "{mn}", falls z.B. "m" nicht akzeptierend und "n" akzeptierend.