Nichtdeterministische Endliche Automaten
Deterministische endliche Automaten beschreiben ziemlich direkt ein Modell zur Berechnung, zur Entscheidung von Sprachenzugehörigkeit. Andererseits kann man es auch anders herum so betrachten, als würde ein deterministischer endlicher Automat eine Sprache beschreiben. Mit dieser Intuition können wir, auch zur formalen Betrachtung, den Automatenbegriff erweitern.
Anders als bisher dürfen jetzt mehrere Kanten mit der selben Beschriftung von einem Status wegführen. Die Transitionsfunktion $\delta$ hat damit eine andere Signatur, nämlich geht sie nicht in die Menge der Zustände, sondern in deren Potenzmenge: $\delta:Z\times{\cal L}\rightarrow{\frak P}(Z)$.
Solche Automaten heißen Nichtdeterministische endliche Automaten. Ein Wort gilt als akzeptiert, wenn es einen Lauf durch den Automaten gibt, der in einem Endzustand endet. Wo deterministische endliche Automaten sich eignen, um Berechnungen zu beschreiben, eignen sich nichtdeterministische endliche Automaten, um Suchprobleme zu beschreiben.
Inhaltsverzeichnis
Beispiele
Beispiel 1
Sei ${\cal L}=\{a,b\}$ und der folgende Automat betrachtet:
+---+ |
| | V
a,b (0)--a-->(1)--a,b-->(2)--a,b-->(3)-- ... -->((k))
| A
+---+
Dieser Automat akzeptiert genau die Wörter, sodass das an $k$-letzter Stelle ein $a$ steht. An diesem Beispiel sieht man gut, dass nichtdeterministische endliche Automaten viel kleiner sein können, als äquivalente deterministische endliche Automaten. Man benötigt einen deterministischen endlichen Automaten mit $2^k$ Zuständen, um dasselbe zu erreichen, zum Beispiel für $k=3$:
+b+ +----------------------+
| | | +-a-+ |
V | V V | |
-->(bbb)---a--->(bba)---a---->(baa)---a--->((aaa)) |
A | A | | |
| b | b b |
| | +--------+ | | |
| V | V | |
| (bab)-----+ | ((aab))<-------+ |
| A | | | | | |
| | a b a b | |
| b | | | | | |
| | V V | V | |
| ((aba)) ((abb)) a |
| | A | | |
| a | b | |
| | | | | |
| +-*------*-----*---------------------+
| | | |
+--------------*------+ |
| |
+------------+
Beispiel 2
Sei ${\cal L}=\{a\}$. Für eine Primzahl $p$ sei folgendes Gadget betrachtet:
*
|
V
((q[p,0]))--a-->(q[p,1])--a-->((q[p,2]))--a-->...--a-->((q[p,p-1])) =: {p}-*
A |
+----------------------------a--------------------------+
Man betrachte nun folgenden Automaten:
+--------a---->{2}
| +------a---->{3}
| |
(q[0])----a---->{5}
| |
| +------a---->{7}
... ...
|
+--------a---->{p}
Sei $q\le p$ eine Primzahl. Ein Wort, dessen Länge $\equiv -1\mod q$ ist, wird nicht in {q} akzeptiert, aber in irgendeinem anderen Gadget. Das kürzteste Wort, das nicht akzeptiert wird, muss also $\equiv -1\mod q$ sein, für alle Primzahlen $q\le p$. Nach dem chinesischen Restsatz hat das kürzeste nicht akzeptierte Wort damit die Länge $2\cdot 3\cdot \ldots\cdot p-1$.
Epsilon-Kanten
Eine nützliche Erweiterung von nichtdeterministischen endlichen Automaten ist die Einführung sogenannter $\varepsilon$-Kanten. Das sind Kanten, die man passieren kann, ohne ein Zeichen zu konsumieren. Beispielsweise akzeptiert folgender Automat
+----ε-----+
| |
V |
(1)---a--->(2)---b--->((3))
beliebige Wörter ab, aab, aaab, etc. $\varepsilon$-Kanten sind praktisch, um Abschlusseigenschaften von Automaten zu zeigen. Allerdings sind sie eine Erweiterung des Automatenmodells. Es ist allerdings möglich, sie zu eliminieren, das heißt, einen äquivalenten Automaten anzugeben, der keine $\varepsilon$-Kanten mehr enthält.
Zunächst betrachten wir drei Zustände $p,q,r$. Bezeichne $A$ die Menge der Übergänge von $p$ nach $q$, und $B$ die Menge der Übergänge von $q$ nach $r$, wir schreiben $p \stackrel{A}{\rightarrow} q \stackrel{B}{\rightarrow} r$. Ist nun $\varepsilon\in A$, das heißt, eine $\varepsilon$-Kante geht von $p$ nach $q$, so fügen wir für jedes Element von $B$ eine Kante von $p$ nach $r$ hinzu (sofern diese nicht schon existiert), das heißt, $p\stackrel{B}{\rightarrow} r$. Analog für $\varepsilon\in B$ Kanten $p\stackrel{A}{\rightarrow} r$.
Wenn wir dies für jedes Tripel $p,q,r$ tun, und immer wieder wiederholen, wird sich irgendwann nichts mehr ändern: Es kann maximal für jedes Zeichen von allen Zuständen zu allen anderen eine Kante geben, und dies sind nur endlich viele, das ist also eine obere Schranke.
Im entstehenden Automaten gibt es für jeden Lauf, der eine $\varepsilon$-Kante enthält, einen äquivalenten Lauf, der diese nicht enthält. Entsprechend können wir jetzt alle $\varepsilon$-Kanten entfernen, ohne die akzeptierte Sprache zu ändern.
Aus obigem Automaten wird beispielsweise
+----a-----+
| |
V |
(1)---a--->(2)---b--->((3))
Potenzmengen-Konstruktion
Die kanonische Frage die sich nun stellt ist, ob nichtdeterministische endliche Automaten mehr können, als deterministische endliche Automaten. Tatsächlich zeigt sich, dass sie das nicht können: Man kann zu jedem nichtdeterministischen endlichen Automaten einen deterministischen endlichen Automaten konstruieren, der die selbe Sprache akzeptiert. Allerdings kann es sein, wie in obigem Beispiel erwähnt, dass man exponentiell viele Zustände bekommt. Dies ist aber in der Praxis eher selten der Fall.
Zunächst sei ein nichtdeterministischer endlicher Automat über dem Alphabet $\cal L$ gegeben, mit Zustandsmenge $Q$, Startzustand $q_0\in Q$, Endzustände $Z\subseteq Q$ und Transitionsfunktion $\delta:Q\times{\cal L}\rightarrow{\frak P}(Q)$. Wir wollen dazu den passenden deterministischen endlichen Automaten definieren.
Dessen Zustandsmenge wird ${\frak P}(Q)$ selbst. Der Startzustand wird das Singleton $\{q_0\}\in{\frak P}(Q)$. Ein Übergang zu einem Zeichen $a\in{\cal L}$ wird dann zwischen $X,Y\subseteq Q$ eingezeichnet, wenn $Y$ genau die Zustände aus $Q$ enthält, die von Zuständen in $X$ mittels eines $a$-Übergangs erreichbar sind, formal $\delta'(X, a) = \bigcup\limits_{x\in X} \delta(x,a)$. Ein Zustand wird Endzustand, wenn mindestens ein Element Endzustand war.
Beispiel
Sei der obige Automat für $k=2$ betrachtet, also
+---+ | | | V a,b (0)--a-->(1)--a,b-->((2)) | A +---+
Die Potenzmenge der Zustände ist $\{\emptyset, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\}$, der neue Startzustand ist also $\{0\}$. Neue Endzustände sind $\{2\},\{1,2\},\{0,1,2\}$. Wir erhalten
+---------------a---------------+ +------------------a---------------+
| | | |
| V | V
-->(0) (1) ((2)) (01) ((02)) ((12)) ((012))
| A | A | A
| | | | | |
+b+ +----a,b----+ +-----b----+
oder, wenn wir die nicht erreichbaren Zustände weglassen,
+---------------a---------------+ +------------------a---------------+
| | | |
| V | V
-->(0) (01) ((02)) ((012))
| A | A
| | | |
+b+ +-----b----+
Abschlusseigenschaften
Wir zeigen hier Abschlusseigenschaften für nichtdeterministische endliche Automaten mit $\varepsilon$-Kanten. Analog zu den obigen Algorithmen kann aus den resultierenden Automaten aber jeweils wieder ein deterministischer endlicher Automat hergestellt werden. Entsprechend sind die Abschlusseigenschaften hier auch Abschlusseigenschaften für deterministische endliche Automaten.
Singletons
Die Sprache, die nur ein einzelnes Wort der Länge 1 enthält, zum Beispiel $\{a\}$, wird akzeptiert von
-->(1)--a-->((2))
Negation/Komplement
Ist eine Sprache $A$ gegeben, und wird von einem Automaten $M$ akzeptiert, so ist ihre Negation oder ihr Komplement definiert durch $\overline{A} := {\cal L}^*\backslash A$. Den Automaten $M$ muss man nur dahingehend verändern, dass man die Rolle von Endzustand und Zwischenzustand vertauscht. Dann werden genau die Wörter akzeptiert, die $M$ nicht akzeptiert.
Konkatenation
Wird eine Sprache $A$ von einem Automaten $M$ mit Endzuständen $q_1,\ldots, q_n$
+------->((q1))
|
--->[M] ...
|
+-------->((qn))
akzeptiert, und eine Sprache $B$ von einem Automaten $N$ mit den Endzuständen $r_1,\ldots, r_k$
+-------->((r1))
|
--->[N] ...
|
+-------->((rk))
so wird die Konkatenation der Sprachen, also die Sprache $AB := \{ab\mid a\in A, b\in B\}$, akzeptiert vom Automaten, bei dem von jedem Endzustand in $M$ eine $\varepsilon$-Kante zum Anfangszustand $N$ gezogen wird, also
+------->(q1)---ε--+ +------>((r1))
| V |
--->[M] ... [N] ...
| A |
+------->(qn)---ε--+ +------>((rk))
Vereinigung
Wird eine Sprache $A$ vom Automaten $M$ akzeptiert, und eine Sprache $B$ vom Automaten $N$ akzeptiert, so wird $A\cup B$ akzeptiert von
+---ε--->[M]
|
--->(1)
|
+---ε--->[N]
Schnitt
Es gilt $A\cap B = \overline{\overline{A}\cup\overline{B}}$.
Kleene-Hülle
Die Kleene-Hülle $A*$ einer Sprache $A$ ist definiert als $\{\varepsilon\}\cup A\cup AA\cup AAA\cup\ldots$, also alle endlichen Wiederholungen von Wörtern aus $A$. Akzeptiert der Automat $M$ mit Anfangszustand $q_0$ und mit Endzuständen $q_1,\ldots,q_n$ die Sprache $A$, so wird $A*$ akzeptiert von
+--ε----------+
| |
| +-->((q1))
V |
---->((q0))-->[M] ...
A |
| +->((qn))
| |
+---ε-------+
