Theoretische Informatik

Nichtdeterministischer endlicher Automat

Mit einem regulären Ausdruck lässt sich eine reguläre Sprache erzeugen. Neben dem Konzept der Erzeugung einer Sprache gibt es das umgekehrte Konzept der Erkennung einer Sprache. Die Erkennung von Sprachen wird mit Automaten durchgeführt.

Die einfachste Art von Automat ist der endliche Automat. Er kann Zeichen auf einem Eingabeband lesen und mithilfe seines Steuerwerks verarbeiten (Bild 1).

Bild 1: Prinzip eines endlichen Automaten

Zu Beginn der Verarbeitung steht ein Wort w Element A* am Anfang des Eingabebandes. Ausgehend von einem Startzustand, arbeitet der Automat das Wort w = w₀ ... w_n-1 zeichenweise ab und vollführt bei jedem Zeichen einen Zustandsübergang. Endet er in einem besonders gekennzeichneten Endzustand, so erkennt er das Wort w, d.h. akzeptiert es als Wort der Sprache, anderenfalls weist er es zurück.

Auf diese Weise lässt sich also ein Automat verwenden, um eine Sprache zu definieren. Die Sprache ist die Menge der Wörter, die der Automat erkennt.

Es folgt die formale Definition des endlichen Automaten, zunächst in der nichtdeterministischen und dann in deterministischen Version.

Definition: Ein nichtdeterministischer endlicher Automat ist ein 5-Tupel

N = (Z, A, d, q, F).

Hierbei ist

`Z`		eine endliche, nichtleere Menge von Zuständen,
`A`		das Eingabealphabet,
`d`		die Übergangsrelation `d` `ZAZ`,
`q` `Z`		der Startzustand,
`F` `Z`		die Menge der Endzustände.

Ein deterministischer endlicher Automat ist ein Spezialfall des nichtdeterministischen endlichen Automaten, bei dem die Übergangsrelation eine Übergangsfunktion ist:

d : Z kreuz A Z

Ein Element (s, a, s') der Übergangsrelation d gibt für das Paar bestehend aus Zustand s und Eingabezeichen a den Zustand s' als möglichen Folgezustand an. D.h. befindet sich der Automat im Zustand s und liest er das Zeichen a als nächstes Eingabezeichen, so kann er den Zustand s' als Folgezustand annehmen.

Beim deterministischen endlichen Automaten ist der Folgezustand für alle (s, a) Element Z kreuz A eindeutig bestimmt. Beim nichtdeterministischen endlichen Automaten kann es zu einem (s, a) Element Z kreuz A mehrere mögliche Folgezustände geben, oder auch gar keinen.

Eine andere Darstellung der Übergangsrelation d eines nichtdeterministischen endlichen Automaten ist die einer Übergangsfunktion f in die Potenzmenge der Zustandsmenge. Dabei ordnet die Übergangsfunktion f jedem Paar aus Zustand und Eingabezeichen eine Menge von möglichen Folgezuständen zu:

f : Z kreuz A Potenzmenge (Z) wobei f(s, a) = { s' | (s, a, s') Element d }

Die Tatsache, dass es beim nichtdeterministischen Automaten im allgemeinen keinen eindeutig bestimmten Folgezustand, sondern mehrere mögliche Folgezustände gibt, ist eine gedanklich schwierige (und erst recht technisch schwer umsetzbare) Konstruktion. Eine Möglichkeit der Vorstellung ist, dass der Automat wählt, welchen von den möglichen Folgezuständen er annimmt. Eine andere Vorstellung ist, dass der Automat entsprechend viele Kopien von sich herstellt, die jeweils in einem der möglichen Folgezustände weiterarbeiten. Eine weitere Vorstellung ist, dass der Automat mehrere Folgezustände gleichzeitig annimmt.

Anschaulich lässt sich das Verhalten eines nichtdeterministischen endlichen Automaten durch seinen Zustandsgraphen darstellen.

Definition: Der Zustandsgraph eines nichtdeterministischen endlichen Automaten (Z, A, d, q, F) ist ein Graph G = (V, E, h). Hierbei ist V = Z, d.h. die Knoten des Graphen sind die Zustände des Automaten; Startzustand und Endzustände werden geeignet gekennzeichnet.

Ein Zustand s ist mit einem Zustand s' durch eine Kante (s, s') verbunden, wenn s' Folgezustand von s unter einem Zeichen a Element A ist, d.h. wenn (s, a, s') Element d gilt.

Die Abbildung h : E Potenzmenge (A) ist eine Kantenbeschriftung; jede Kante (s, s') ist mit der Menge aller Zeichen beschriftet, unter denen Zustand s nach Zustand s' übergeht.

Beispiel: In Bild 2a ist der Zustandsgraph eines nichtdeterministischen endlichen Automaten abgebildet, hierbei sind die Mengenklammern um die Beschriftungen der Kanten weggelassen.

Die Zustandsmenge ist Z = {0, ..., 3}, der Startzustand ist q = 0, die Menge der Endzustände ist F = {2, 3}, und das Eingabealphabet ist A = {a, b}. Die Übergangsrelation d enthält folgende Zustandsübergänge:

(0, a, 1)
(0, a, 2)
(2, a, 2)
(1, a, 1)
(1, b, 1)
(1, a, 3)

Definition: Sei e₀ ... e_n-1 mit e_i Element E, n Element natürliche Zahlen ₀ ein Pfad, also eine endliche Folge von aufeinanderfolgenden Kanten, im Zustandsgraphen G eines nichtdeterministischen endlichen Automaten.

Wir fassen die Kantenbeschriftungen als Elementarsprachen auf. Dann ergibt sich die Beschriftung des Pfades als Verkettung der Beschriftungen seiner Kanten:

h(e₀ ... e_n-1) = h(e₀)·... ·h(e_n-1).

Die Beschriftung eines Pfades ist also eine Sprache.

Definition: Ein nichtdeterministischer endlicher Automat N erkennt (akzeptiert) das Wort w, wenn es in seinem Zustandsgraphen einen Pfad vom Startzustand zu einem Endzustand gibt, dessen Beschriftung das Wort w enthält. Die Menge aller Wörter, die N erkennt, ist die von N erkannte Sprache L(N).

Formal ist die vom Automaten N erkannte Sprache

L(N) = { w = w₀ ... w_n-1 | (s_i, w_i, s_i+1) Element d, i Element {0, ..., n-1}, s_i Element Z, s₀ = q Startzustand, s_n Element F }

d.h. es gibt eine Kette von Zustandsübergängen mit den Zeichen von w vom Startzustand q zu einem Endzustand.

Beispiel: Im Zustandsgraphen des nichtdeterministischen endlichen Automaten ist in Bild 2b ein Pfad vom Startzustand zu einem Endzustand hervorgehoben. Die Beschriftung des Pfades ergibt sich als {aaa, aba}, sie enthält das Wort w = aba. Das Wort aba wird also von dem Automaten erkannt. Die Kette der Zustandsübergänge für aba ist (0, a, 1), (1, b, 1), (1, a, 3).

Bild 2: Zustandsgraph eines nichtdeterministischen endlichen Automaten (a), Pfad vom Startzustand zu einem Endzustand (b)

In unserer Vorstellung von der Arbeitsweise eines nichtdeterministischen endlichen Automaten ergibt sich der in diesem Beispiel hervorgehobene Pfad dadurch, dass der Automat ausgehend vom Startzustand immer die richtigen Zustandsübergänge wählt, die mit dem Eingabewort w zu einem Endzustand führen – wie ein Schlafwandler, der auch seine Schritte immer richtig setzt, ohne zu wissen wo er ist und wohin er will.

Es ist im allgemeinen nicht offensichtlich, ob ein gegebener nichtdeterministischer endlicher Automat ein bestimmtes Wort w erkennt, d.h. ob es in seinem Zustandsgraphen einen Pfad gibt, dessen Beschriftung das Wort w enthält. Dies lässt sich jedoch herausfinden, indem eine Breitensuche im Zustandsgraphen des Automaten durchgeführt wird. Dieses Verfahren wird als Simulation des Automaten bezeichnet.

Die Simulation eines nichtdetermistischen endlichen Automaten kann man sich als eine Art "Mensch-ärgere-dich-nicht"-Spiel vorstellen. Der Zustandsgraph des Automaten ist das Spielbrett. Zustände werden markiert, indem nach bestimmten Regeln Spielsteine auf die Felder gesetzt werden. Es gibt nur einen Spieler; dieser liest die Zeichen des zu untersuchenden Wortes w.

Zu Beginn der Simulation wird ein Spielstein auf den Startzustand gesetzt. Für jedes Zeichen des Eingabewortes w wird dann folgender Zug ausgeführt:

Wird das Zeichen a gelesen, so rücken alle Spielsteine, die einen Übergang mit dem Zeichen a machen können, auf das entsprechende Feld vor. Spielsteine, die auf mehrere Felder vorrücken können, werden geklont (Bild 3). Alle Spielsteine, die keinen Übergang mit dem Zeichen a machen können, werden entfernt (Bild 4).

Das Spiel ist "gewonnen", wenn nach Einlesen aller Zeichen des Wortes w ein Spielstein auf einem Endzustand steht. Der Automat hat dann das Wort w erkannt.

Bild 3: Zustandsübergang bei gelesenem Zeichen a

Bild 4: Zustandsübergang bei gelesenem Zeichen a

Es folgt die formale Beschreibung des Verfahrens zur Simulation eines nichtdeterministischen endlichen Automaten.

Markiere den Startzustand;
Für jedes gelesene Eingabezeichen:
- Markiere alle Folgezustände unter dem Eingabezeichen;

Ist am Ende ein Endzustand markiert, so hat der Automat das Eingabewort erkannt.

Die Simulation des nichtdeterministischen endlichen Automaten entspricht unserer Vorstellung, dass der Automat sich in mehreren Zuständen gleichzeitig befinden kann, nämlich den markierten Zuständen.

(Java-Applet zur Simulation eines nichtdeterministischen endlichen Automaten)

Weiter: [Nichtdeterministischer endlicher Automat mit Epsilon-Übergängen] oder