5.3 Nichtdeterministische endliche Automaten

Ein nichtdeterministischer Automat ist, informell ausgedrückt, wie ein deterministischer Automat, nur dass es für eine Zustand-Symbol-Kombination beliebig viele ausgehende Pfeile (eventuell gar keinen) geben kann. Hier ist das Beispiel von vorhin, leicht abgewandelt:

Ein Pfeil beschreibt also nicht unbedingt einen Zustandsübergang, der geschieht, sondern einen, der möglich ist. Formal gesprochen ist $δ$ nun keine Funktion mehr, sondern eine Relation:

Definition 5.3.1 (Nichtdeterministischer endlicher Automat, non-deterministic finite state machine) Ein nichtdeterministischer endlicher Automat besteht aus

einem endlichen Eingabealphaet $Σ$ ,
einer endlichen Menge $Q$ von Zuständen,
einem Startzustand $q_{s t a r t} \in Q$ ,
einer Menge $F \subseteq Q$ von akzeptierenden Endzuständen,
einer Zustandsübergangsrelation $δ \subseteq Q \times Σ \times Q$ .

Formal gesehen ist also ein Automat ein Quintupel

M = (Σ, Q, q_{s t a r t}, F, δ)

Von nun an bezeichnen wir endliche Automaten auch als deterministische endliche Automaten, um den Unterschied zu den nichtdeterministischen zu verdeutlichen. Wenn in einem deterministischen endlichen Automaten

δ (q, x) = q^{'}

war, so hatte das die Bedeutung wenn der Automat im Zustand $q$ ist und $x$ liest, so geht er in Zustand $q^{'}$ über; wenn nun in einem nichtdeterministischen Automaten

(q, x, q^{'}) \in δ

gilt, so bedeutet das, wenn der Automat im Zustand $q$ ist und $x$ liest, so kann er in Zustand $q^{'}$ übergehen. Analog zu den deterministischen Automaten definieren wir eine erweiterte Zustandsübergangsrelation.

Definition 5.3.2 (Erweiterte Zuständsübergangsfunktion). Für einen nichtdeterministischen endlichen Automaten

(Σ, Q, q_{s t a r t}, F, δ)

definieren wir die erweiterte Zustandsübergangsrelation

\hat{δ} \subseteq Q \times Σ^{*} \to Q

als die Menge aller Zustand-Wort-Zustand-Tripel

(q, x_{1} x_{2} \dots x_{n}, q^{'})

, für die wir Zwischenzustände

q = q_{s t a r t}, q_{1}, q_{2}, \dots, q_{n} = q^{'}

finden können mit

(q_{s t a r t}, x_{1}, q_{1}), (q_{1}, x_{2}, q_{2}), \dots, (q_{n - 1}, x_{n}, q_{n}) \in δ

Dies schließt den Fall

n = 0

mit ein, also

(q, ϵ, q) \in \hat{δ}

. Wie zuvor schreiben wir

q \overset{α}{\to} q^{'}

Die von $M$ akzeptierte Sprache ist $L (M) := {α \in Σ^{*} | es gibt ein q \in F mit q_{s t a r t} \overset{α}{\to} q}$

Beobachtung 5.3.3 Sei

M = (Σ, Q, q_{s t a r t}, F, δ)

ein nichtdeterministischer endlicher Automat. Dann gibt es eine reguläre Grammatik

G

mit

L (G) = L (M)

Wir führen hier den Beweis nicht noch einmal; er ist mehr oder weniger identisch mit dem Beweis von Theorem 4.2.5; wir haben nämlich in jenem Beweis nirgends verwendet, dass $δ$ eine Funktion ist, und daher geht mit einem $δ$ , das eine Relation ist, alles ganz genau gleich. Allerdings gilt nun auch der Umkehrschluss: zu einer regulären Grammatik gibt es einen nichtdeterministischen endlichen Automaten:

Theorem 5.3.4 Sei

G = (Σ, N, P, S)

eine reguläre Grammatik. Dann gibt es einen nichtdeterministischen endlichen Automaten

M

mit

L (G) = L (M)

Beweis. Unser Automat hat als Zustandsmenge

N

, die Menge der nichtterminalen Symbole und als Startzustand

S

, das Startsymbol der Grammatik

G

. Wir definieren

δ

, indem wir jeden

G

-Pfeil in einem

M

-Pfeil umwandeln: eine Produktion

X \to a Y

G

wird dann zu

(X, a, Y) \in δ

also einem Pfeil

X \overset{a}{\to} Y

M

. Für jede Regel der Form

X \to ϵ

machen wir

X

zu einem Endzustand.

Was aber mit Regeln der Form $X \to Y$ ? Hierfür könnte man Nichtdeterministische Automaten mit $ϵ$ -Übergängen definieren, die also vom Zustand $X$ nach $Y$ wechseln können, ohne ein Eingabesymbol zu lesen; wir gehen hier einen anderen Weg und verweisen auf Theorem 4.1.7, welches uns erlaubt, Regeln der Form $X \to Y$ und $X \to a$ zu eliminieren. $◻$

Beispiel 5.3.5

Wir betrachten abermals die reguläre Grammatik aus dem vorherigen Kapitel 4.1: $\begin{aligned} S & \to ϵ | a S | b T \\ T & \to ϵ | b T \end{aligned}$ und auch den (falschen) endlichen Automaten, den wir im letzten Kapitel dafür gebaut haben:

Wir sehen nun, dass dies genau der nichtdeterministische Automat ist, den wir nach Theorem 4.3.4 bauen können. Die Zustandsübergangsrelation $δ$ ist $δ = {(S, a, S), (S, b, S), (T, b, T)} .$ Jeder Zustand ist ein Endzustand, allerdings heißt das nicht, dass der Automat jedes Wort akzeptiert. Für $α = b a$ beispielsweise gibt es keinen Zustand $q$ mit $S \overset{b a}{\to} q$ , geschweige denn einen akzeptierenden Endzustand. Daher gilt: $b a \notin L (M)$ .

Beispiel 5.3.6

Wir betrachten die reguläre Grammatik aus Übungsaufgabe 4.1.7:

\begin{aligned} S & \to A | B \\ A & \to ϵ | b A | c A \\ B & \to ϵ | a B | c B \end{aligned}

Bevor wir einen nichtdeterministischen Automaten bauen können, müssen wir erst die Produktionen der Form $X \to Y$ eliminieren bzw. ersetzen. Wenn Sie Aufgabe 4.1.7 gelöst haben, haben Sie wahrscheinlich in etwa folgende Grammatik erhalten:

\begin{aligned} S & \to ϵ | b A | c A | a B | c B \\ A & \to ϵ | b A | c A \\ B & \to ϵ | a B | c B \end{aligned}

Also insgesamt 11 statt 8 Produktionen. Alle Nichtterminale erlauben auf ihrer rechten Seite ein

ϵ

und werden so zu akzeptierenden Zuständen. Die Zustandsübergangsrelation

δ

ist also

\begin{aligned} δ & = {(S, b, A), (S, c, A), (S, a, B), (S, c, B), (A, b, A), (A, c, A), (B, a, B), (B, c, B)} \end{aligned}

Der nichtdeterminische Automat schaut also so aus:

Übungsaufgabe 5.3.1 Sei

Σ = {1}

und

L_{k} := {1^{n} | n ist durch k teilbar}

. Schreiben Sie für

L_{k}

einen deterministischen endlichen Automaten.

Schreiben Sie eine reguläre Grammatik für die Sprache $L_{5} \cup L_{7}$ , also die Strings aus 1, deren Länge durch 5 oder durch 7 teilbar ist.

Zeichnen Sie nun einen nichtdeterministischen endlichen Automaten für $L_{5} \cup L_{7}$ .

Nichtdeterministische endliche Automaten deterministisch machen

Wir werden nun zeigen, dass man zu jedem nichtdeterministischen Automaten $M$ einen äquivalenten deterministischen Automaten $M^{'}$ bauen kann. Bevor wir eine allgemeine Konstruktion zeigen, fragen wir uns, wie wir beispielsweise für den nichtdeterministischen endlichen Automaten $M$ :

und das Eingabewort $α = 1001100$ überprüfen können, ob $1001100 \in L (M)$ gilt. Einem determinischen endlichen Automaten können wir ja das Eingabewort einfach füttern und schauen, was der Automat tut; bei nichtdeterministischen Automaten müssen wir schauen, was er alles tun könnte. Wir plazieren einen kleinen farbigen Punkt in jeden Zustand, in dem sich der Automat befinden könnte; am Anfang hat der Startzustand $A$ einen roten Punkt.

Am Ende landet der grüne Punkt im Zustand $E$ . Das Wort ist also in $L (M)$ . Das können wir auch ganz allgemein tun. Wenn Zustand $q$ einen "Punkt" hat und Zeichen $x$ gelesen wird, dann teilt sich dieser Punkt und plaziert einen Kind-Punkt in jedem Zustand $q^{'}$ , für den $q \overset{x}{\to} q^{'}$ gilt. Formal gesprochen: für eine Menge $R \subseteq Q$ von Zuständen (die, die gerade einen "Punkt" haben) und ein Eingabe-Symbol $x$ definieren wir $\begin{array}{r} Δ (R, x) := {q^{'} \in Q | es gibt q \in R mit q \overset{x}{\to} q^{'}} \end{array}$ Für ein Eingabewort $α = x_{1} \dots x_{n}$ fangen wir nun mit $R_{0} = {q_{s t a r t}}$ an, das entspricht dem einen roten Punkt auf dem Startzustand, und berechnen dann jeweils $R_{i} = Δ (R_{i - 1}, x_{i})$ ; wenn die Menge $R_{n}$ einen akzeptierenden Endzustand enthält (dieser also am Ende einen "Punkt" hat), gilt $α \in L (M)$ .

Treten Sie einen Schritt zurück und betrachten, was wir mit $Δ$ definiert haben: wir haben eine Zustandsübergangsfunktion definiert, die nun aber nicht auf Zuständen sondern auf Zustandsmengen operiert. Das heißt, im Gegensatz zu $δ$ , das eine Funktion $δ : Q \times Σ \to Q$ ist, ist $\begin{array}{r} Δ : 2^{Q} \times Σ \to 2^{Q} . \end{array}$ Wenn Sie die Schreibweise $2^{Q}$ nicht kennen: dies ist die Potenzmenge von $Q$ , also die Menge aller Untermengen, was die leere Menge $\emptyset$ und die "volle Menge" $Q$ selbst miteinschließt. Wir haben also folgendes Theorem:

Theorem 5.3.7 (Einen nichtdeterministischen endlichen Automaten deterministisch machen). Sei

M = (Σ, Q, q_{s t a r t}, F, δ)

ein nichtdeterministischer Automat; dann heiße der deterministische Automat

M^{'} = (Σ, 2^{Q}, {q_{s t a r t}}, F, Δ)

mit Endzustandsmenge

F

definiert als

\begin{array}{r} F := {X \subseteq Q | X \cap F \neq \emptyset} \end{array}

und Zustandsübergangsfunktion

Δ

definiert als

\begin{aligned} Δ : & 2^{Q} \times Σ \to 2^{Q} \\ (R, x) \mapsto {q^{'} \in Q | es gibt q \in R mit q \overset{x}{\to} q^{'}} \end{aligned}

der Potenzmengenautomat. Es gilt

L (M) = L (M^{'})

Wir folgern also

Theorem 5.3.8 Zu jeder regulären Sprache

L

gibt es einen deterministischen endlichen Automaten

M

mit

L (M) = L

Beispiel 5.3.9 Der obige nichtdeterminische Automaten

M

, der die Sprache aller Wörter, deren viertletztes Zeichen eine 1 ist, akzeptiert, hat fünf Zustände. Sein Potenzmengenautomat

M^{'}

hätte also

2^{5} = 32

. Allerdings sehen wir, dass alle "relevanten" Zustände von

M

den Zustand

A

enthalten. Dieser wird nie verschwinden. Also sehen wir, dass man

M^{'}

mit 16 Zuständen implementieren kann (die anderen, die, die nicht

A

enthalten, sind unerreichbar). Da 16 immer noch recht groß für eine Abbildung ist, nehmen wir uns die Sprache aller Wörter, deren drittletztes Zeichen eine 1 ist. Der nichtdeterministische Automat hierfür ist

Der Potenzmengenautomat hat die Zustandsmenge

\begin{array}{r} {\emptyset, A, B, C, D, A B, A C, A D, B C, B D, C D, A B C, A B D, A C D, B C D, A B C D} \end{array}

wobei wir der Lesbarkeit halber $A B$ statt ${A, B}$ etc. schreiben. Um bei der Konstruktion des Potenzmengenautomaten unnötige Zustände zu vermeiden, bauen wir ihn Schritt für Schritt, angefangen mit dem Startzustand ${A}$ bzw. $A$ , und hängen jedem Zustand einen ausgehenden $0$ -Pfeil und $1$ -Pfeil an, wobei wir womöglich neue Zustände "entdecken".

Wenn wir uns vorstellen, dass wir vor das Eingabewort $α$ die Zeichen 000 stellen, also $α$ durch $000 α$ ersetzen, dann codiert jeder Zustand genau die letzten drei Zeichen des Eingabewortes, die der Automat gelesen hat. Der Zustand $A C D$ bedeutet zum Beispiel die letzten drei Zeichen waren $110$

Im folgenden Unterkapitel werden wir alle Transformationen, die wir bisher gesehen haben, an einem konkreten Beispiel anwenden.