Theoretische Informatik

Nichtdeterministischer endlicher Automat

 aufwärts

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
Bild 1: Prinzip eines endlichen Automaten

Zu Beginn der Verarbeitung steht ein Wort x Element A* am Anfang des Eingabe­bandes. Der Automat nimmt in seinem Steuerwerk während der Verarbeitung bestimmte Zustände an. Ausgehend von einem Startzustand, arbeitet der Automat das Wort x = x0 ... xn-1 zeichenweise ab und vollführt bei jedem Zeichen einen Zustands­übergang. Endet er in einem besonders gekenn­zeichneten Endzustand, so erkennt er das Wort x, 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.

Einfaches Beispiel

Die Arbeitsweise des Automaten lässt sich mithilfe seines Zustands­graphen sehr anschaulich darstellen. Folgendes sehr einfache Beispiel zeigt den Zustands­graphen eines endlichen Automaten. Die beiden Zustände des Automaten sind als Kreise dargestellt und mit g und u bezeichnet. Die Pfeile, mit denen die Zustände verbunden sind, stellen mögliche Zustands­übergänge dar. Sie sind mit Zeichen des zugrunde­liegenden Eingabe­alphabets beschriftet. Der Automat in diesem Beispiel kann einen Zustands­übergang vollführen, wenn er sich im Zustand g befindet und das Zeichen a auf dem Eingabeband liest; er geht dann in den Zustand u über. Befindet er sich im Zustand u und liest als nächstes Zeichen auf dem Eingabeband ein b, so geht er in den Zustand g über.

Bild 2: Zustandsgraph eines endlichen Automaten
Bild 2: Zustandsgraph eines endlichen Automaten

Der Automat startet im Zustand g, dieser ist der Startzustand des Automaten, gekenn­zeichnet durch einen kleinen Pfeil, der auf diesen Zustand zeigt. Wenn der Automat nun auf dem Eingabeband das Zeichen a oder das Zeichen b liest, arbeitet er es ab und geht in den Zustand u über. Dieser Zustand ist ein Endzustand, gekenn­zeichnet durch einen doppelten Kreis. Solange aber der Automat das Eingabewort noch nicht vollständig abgearbeitet hat, ist es bedeutungs­los, ob er sich in einem Endzustand befindet oder nicht. Er liest dann weitere Zeichen auf dem Eingabeband und vollführt die ent­sprechenden Zustands­übergänge. Erst wenn der Automat das Eingabewort vollständig abgearbeitet hat, dann kommt es darauf an, ob er sich in einem Endzustand befindet oder nicht. Befindet er sich in einem Endzustand, erkennt er das Eingabewort, anderenfalls weist er es zurück.

Der obige Automat erkennt genau die Sprache aller Wörter über dem Alphabet A = {a, b}, die eine ungerade Länge haben, also eine Länge von 1, 3, 5, 7, ... . Denn immer, wenn ein Wort ungerader Länge auf dem Eingabeband steht und der Automat es abarbeitet, endet er im Zustand u, und dieser Zustand ist ein Endzustand. Also erkennt er das Wort. Andererseits, wenn ein Wort gerader Länge auf dem Eingabeband steht und der Automat es abarbeitet, endet er im Zustand g, und dieser Zustand ist kein Endzustand. Also erkennt er das Wort nicht.

Wie sieht ein Automat aus, der alle Wörter gerader Länge erkennt, also der Länge 0, 2, 4, 6, ... ?

Formale Definition

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

Definition:  Ein nicht­deterministischer endlicher Automat ist ein 5-Tupel

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

Hierbei ist

Z eine endliche, nichtleere Menge von Zuständen,
A das Eingabe­alphabet,
d die Übergangs­relation   d  enthalten in  Z × A × Z,
q Element Z    der Startzustand,
F enthalten in Z die Menge der Endzustände.

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

d : Z × A Pfeil nach rechts Z

Ein Element (s, a, s') der Übergangs­relation d gibt für das Paar bestehend aus Zustand s und Eingabe­zeichen 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 Eingabe­zeichen, so kann er den Zustand s' als Folgezustand annehmen.

Beim deterministischen endlichen Automaten ist der Folgezustand für alle (s, aElement Z × A eindeutig bestimmt. Beim nicht­deterministischen endlichen Automaten kann es zu einem (s, aElement Z × A mehrere mögliche Folge­zustände geben, oder auch gar keinen.

 

Die Tatsache, dass es beim nicht­deterministischen Automaten im allgemeinen keinen eindeutig bestimmten Folgezustand, sondern mehrere mögliche Folge­zustä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 Folge­zuständen er annimmt. Eine andere Vorstellung ist, dass der Automat entsprechend viele Kopien von sich herstellt, die jeweils in einem der möglichen Folge­zustände weiter­arbeiten. Eine weitere Vorstellung ist, dass der Automat mehrere Folge­zustände gleichzeitig annimmt.

Zustandsgraph

Wie bereits gesehen, lässt sich das Verhalten eines nicht­deterministischen endlichen Automaten anschaulich durch seinen Zustands­graphen darstellen.

Definition:  Der Zustands­graph eines nicht­deterministischen endlichen Automaten N = (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 gekenn­zeichnet.

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 ist eine Kanten­beschriftung; jede Kante (s, s') ist mit denjenigen Zeichen beschriftet, unter denen Zustand s nach Zustand s' übergeht.

Es kann sein, dass ein Zustand s sowohl unter einem Zeichen a als auch unter einem Zeichen b in denselben Folgezustand s' übergeht. Wir zeichnen dann nicht zwei Kanten von s nach s', sondern nur eine Kante und beschriften diese mit beiden Zeichen a und b.

Aus technischen Gründen fassen wir die Kanten­beschriftungen nicht als Mengen von Alphabet­zeichen auf, sondern als Mengen von Wörtern der Länge 1. Damit sind die Kanten­beschriftungen nichts anderes als Elementar­sprachen. Für die Abbildung h gilt also h : E Pfeil nach rechts e, wobei e = Potenzmenge(A1) die Menge der Elementar­sprachen über dem Alphabet A ist.

Bei der Darstellung von Zustands­graphen lassen wir der Über­sicht­lich­keit halber bei den Kanten­beschriftungen die Mengen­klammern weg.

Beispiel:  In Bild 3a ist der Zustands­graph eines nicht­deterministischen endlichen Automaten abgebildet.

Die Zustands­menge ist Z = {0, ..., 3}, der Startzustand ist q = 0, die Menge der Endzustände ist F = {2, 3}, und das Eingabe­alphabet ist A = {a, b}. Die Übergangs­relation d besteht aus folgenden Zustands­übergängen:

d  =  { (0, a, 1), (0, a, 2), (2, a, 2), (1, a, 1), (1, b, 1), (1, a, 3) }

bzw. über­sicht­licher in Form einer Tabelle dargestellt:

 

sas'
0a1
0a2
2a2
1a1
1b1
1a3

Definition:  Sei e0 ... en-1 mit ei Element E, n Element natürliche Zahlen0 ein Pfad, also eine endliche Folge von aufeinander­folgenden Kanten, im Zustands­graphen G eines nicht­deterministischen endlichen Automaten.

Die Beschriftungen der Kanten sind Elementar­sprachen. Sprachen lassen sich miteinander verketten. Die Beschriftung eines Pfades ergibt sich als Verkettung der Beschriftungen seiner Kanten:

h(e0 ... en-1)  =  h(e0) ... h(en-1).

Die Beschriftung eines Pfades ist also eine Sprache.

Definition:  Ein nicht­deterministischer endlicher Automat N erkennt das Wort w, wenn es in seinem Zustands­graphen 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).

Beispiel:  Im Zustands­graphen des nicht­deterministischen endlichen Automaten ist in Bild 3b ein Pfad vom Startzustand zu einem Endzustand hervor­gehoben. Die Beschriftung des Pfades ergibt sich als Verkettung der Elementar­sprachen, mit denen seine Kanten markiert sind, also als {a}{a, b}{a} = {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 3: Zustandsgraph eines nichtdeterministischen endlichen Automaten (a), Pfad vom Startzustand zu einem Endzustand (b)
Bild 3: Zustandsgraph eines nichtdeterministischen endlichen Automaten (a), Pfad vom Startzustand zu einem Endzustand (b)

In unserer Vorstellung von der Arbeitsweise eines nicht­deterministischen endlichen Automaten ergibt sich der in diesem Beispiel hervor­gehobene 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 Schlaf­wandler, der seine Schritte immer richtig setzt, ohne zu wissen wo er ist und wohin er will.

Simulation eines nichtdeterministischen endlichen Automaten

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

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

Zu Beginn der Simulation wird eine Spielfigur auf den Startzustand gesetzt. Für jedes Zeichen des Eingabe­wortes w wird dann folgender Zug ausgeführt:

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

Bild 4: Zustandsübergang bei gelesenem Zeichen a
Bild 4: Zustandsübergang bei gelesenem Zeichen a
Bild 5: Zustandsübergang bei gelesenem Zeichen a
Bild 5: Zustandsübergang bei gelesenem Zeichen a

 

Es folgt die formale Beschreibung des Verfahrens zur Simulation eines nicht­deterministischen endlichen Automaten.

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

 

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

Simulation

 

(Java-Applet zur Simulation eines nichtdeterministischen endlichen Automaten)

Übergangsrelation

Derselbe Automat ist hier durch seine Übergangs­relation dargestellt. Er kann in dieser Form hier ebenfalls simuliert werden. Bei nicht­deterministischer Wahl­möglichkeit ist dasjenige Tupel der Übergangs­relation anzuklicken, das den Zustands­übergang bewirken soll.

 

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
 0 a1
 0 a2*
 2 a2*
 1 a1
 1 b1
 1 a3*


 

Übung

Aufgabe 1:  Entwerfen Sie einen nicht­deterministischen endlichen Automaten, der folgende Sprache L über dem Alphabet A = {a, b} erkennt:

L  =  { w | w endet auf bb }

Zeichnen Sie zunächst den Zustands­graphen des Automaten. Übertragen Sie dann die Übergangs­relation des Automaten in die folgende Tabelle und simulieren Sie den Automaten.

 

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     

       


 

Aufgabe 2:  Entwerfen Sie einen nicht­deterministischen endlichen Automaten, der folgende Sprache L über dem Alphabet A = {a, b} erkennt:

L  =  { w | w enthält eine gerade Anzahl von b's }

Zeichnen Sie zunächst den Zustands­graphen des Automaten. Übertragen Sie dann die Übergangs­relation des Automaten in die folgende Tabelle und simulieren Sie den Automaten.

 

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sas'
     
     
     
     
     
     

       


 

Erweiterung der Übergangsrelation auf Wörter

Wir haben anschaulich anhand des Zustands­graphen definiert, wann ein Eingabewort w vom Automaten erkannt wird. Dies ist dann der Fall, wenn es im Zustands­graphen einen Pfad vom Startzustand q zu einem Endzustand t gibt, dessen Beschriftung das Wort w enthält.

Wir definieren dies nun formal; hierzu erweitern wir zunächst die Übergangs­relation d eines nicht­deterministischen endlichen Automaten auf ganze Wörter.

Definition:  Sei N = (Z, A, d, q, F) ein nicht­deterministischer endlicher Automat mit Übergangs­relation d Element Z × A × Z. Die Übergangs­relation d wird zu einer erweiterten Übergangs­relation denthalten in Z × A* × Z in folgender Weise erweitert:

  1. für alle Zustände s Element Z ist  (s, ε, sElement d*
  2. wenn  (r, v, sElement d*  und  (s, a, tElement d, so ist auch  (r, va, tElement d*

Es gilt also (s, w, tElement d*, wenn es im Zustands­graphen des Automaten einen Pfad vom Zustand s zum Zustand t gibt, dessen Beschriftung das Wort w enthält. Der Automat erkennt dieses Wort w, wenn s der Startzustand und t ein Endzustand ist. Die ent­sprechende Definition mithilfe der erweiterten Übergangs­relation d* lautet wie folgt.

Definition:  Sei N = (Z, A, d, q, F) ein nicht­deterministischer endlicher Automat. Der Automat N erkennt das Wort w, wenn es einen Endzustand t Element F gibt, der vom Startzustand q mit dem Wort w erreichbar ist:

(q, w, tElement d*

Die von N erkannte Sprache ist somit

L(N)  =   { w Element A*  |   es existiert t Element F :  (q, w, tElement d* }

Äquivalenz von Automaten

Wir hatten bereits bei der Behandlung der regulären Ausdrücke gesehen, dass es unterschiedliche reguläre Ausdrücke geben kann, die dieselbe Sprache erzeugen. Zwei solche Ausdrücke hatten wir als äquivalent bezeichnet. Entsprechend definieren wir nun Äquivalenz bei Automaten.

Definition:  Zwei nicht­deterministische endliche Automaten N und M werden als äquivalent bezeichnet, wenn sie dieselbe Sprache erkennen, d.h. wenn gilt

L(N)  =  L(M).

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   Updated: 09.09.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik