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:

    +---+
    |   |
   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$:

TODO

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