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.

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))