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 x ∈ A* am Anfang des Eingabebandes. 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 gekennzeichneten 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.
Die Arbeitsweise des Automaten lässt sich mithilfe seines Zustandsgraphen sehr anschaulich darstellen. Folgendes sehr einfache Beispiel zeigt den Zustandsgraphen 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 Eingabealphabets 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
Der Automat startet im Zustand g, dieser ist der Startzustand des Automaten, gekennzeichnet 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, gekennzeichnet durch einen doppelten Kreis. Solange aber der Automat das Eingabewort noch nicht vollständig abgearbeitet hat, ist es bedeutungslos, ob er sich in einem Endzustand befindet oder nicht. Er liest dann weitere Zeichen auf dem Eingabeband und vollführt die entsprechenden 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, ... ?
Es folgt die formale Definition des endlichen Automaten, zunächst in der nichtdeterministischen und dann in der 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 ⊆ Z × A × Z, | |
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 × 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) ∈ Z × A eindeutig bestimmt. Beim nichtdeterministischen endlichen Automaten kann es zu einem (s, a) ∈ Z × A mehrere mögliche Folgezustände geben, oder auch gar keinen.
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.
Wie bereits gesehen, lässt sich das Verhalten eines nichtdeterministischen endlichen Automaten anschaulich durch seinen Zustandsgraphen darstellen.
Definition: Der Zustandsgraph eines nichtdeterministischen 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 gekennzeichnet.
Ein Zustand s ist mit einem Zustand s' durch eine Kante (s, s') verbunden, wenn s' Folgezustand von s unter einem Zeichen a ∈ A ist, d.h. wenn (s, a, s') ∈ d gilt.
Die Abbildung h ist eine Kantenbeschriftung; 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 Kantenbeschriftungen nicht als Mengen von Alphabetzeichen auf, sondern als Mengen von Wörtern der Länge 1. Damit sind die Kantenbeschriftungen nichts anderes als Elementarsprachen. Für die Abbildung h gilt also h : E → ℒe, wobei ℒe = (A1) die Menge der Elementarsprachen über dem Alphabet A ist.
Bei der Darstellung von Zustandsgraphen lassen wir der Übersichtlichkeit halber bei den Kantenbeschriftungen die Mengenklammern weg.
Beispiel: In Bild 3a ist der Zustandsgraph eines nichtdeterministischen endlichen Automaten abgebildet.
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 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. übersichtlicher in Form einer Tabelle dargestellt:
s | a | s' |
---|---|---|
0 | a | 1 |
0 | a | 2 |
2 | a | 2 |
1 | a | 1 |
1 | b | 1 |
1 | a | 3 |
Definition: Sei e0 ... en-1 mit ei ∈ E, n ∈ ℕ0 ein Pfad, also eine endliche Folge von aufeinanderfolgenden Kanten, im Zustandsgraphen G eines nichtdeterministischen endlichen Automaten.
Die Beschriftungen der Kanten sind Elementarsprachen. 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 nichtdeterministischer endlicher Automat N erkennt 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).
Beispiel: Im Zustandsgraphen des nichtdeterministischen endlichen Automaten ist in Bild 3b ein Pfad vom Startzustand zu einem Endzustand hervorgehoben. Die Beschriftung des Pfades ergibt sich als Verkettung der Elementarsprachen, 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)
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 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 nichtdeterministischen 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 Spielfiguren auf die Felder gesetzt werden. Es gibt nur einen Spieler; dieser liest die Zeichen des zu untersuchenden Wortes w.
Zu Beginn der Simulation wird eine Spielfigur auf den Startzustand gesetzt. Für jedes Zeichen des Eingabewortes 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 5: Zustandsübergang bei gelesenem Zeichen a
Es folgt die formale Beschreibung des Verfahrens zur Simulation eines nichtdeterministischen endlichen Automaten.
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)
Derselbe Automat ist hier durch seine Übergangsrelation dargestellt. Er kann in dieser Form hier ebenfalls simuliert werden. Bei nichtdeterministischer Wahlmöglichkeit ist dasjenige Tupel der Übergangsrelation anzuklicken, das den Zustandsübergang bewirken soll.
Aufgabe 1: Entwerfen Sie einen nichtdeterministischen endlichen Automaten, der folgende Sprache L über dem Alphabet A = {a, b} erkennt:
L = { w | w endet auf bb }
Zeichnen Sie zunächst den Zustandsgraphen des Automaten. Übertragen Sie dann die Übergangsrelation des Automaten in die folgende Tabelle und simulieren Sie den Automaten.
Aufgabe 2: Entwerfen Sie einen nichtdeterministischen 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 Zustandsgraphen des Automaten. Übertragen Sie dann die Übergangsrelation des Automaten in die folgende Tabelle und simulieren Sie den Automaten.
Wir haben anschaulich anhand des Zustandsgraphen definiert, wann ein Eingabewort w vom Automaten erkannt wird. Dies ist dann der Fall, wenn es im Zustandsgraphen 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 Übergangsrelation d eines nichtdeterministischen endlichen Automaten auf ganze Wörter.
Definition: Sei N = (Z, A, d, q, F) ein nichtdeterministischer endlicher Automat mit Übergangsrelation d ∈ Z × A × Z. Die Übergangsrelation d wird zu einer erweiterten Übergangsrelation d* ⊆ Z × A* × Z in folgender Weise erweitert:
Es gilt also (s, w, t) ∈ d*, wenn es im Zustandsgraphen 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 entsprechende Definition mithilfe der erweiterten Übergangsrelation d* lautet wie folgt.
Definition: Sei N = (Z, A, d, q, F) ein nichtdeterministischer endlicher Automat. Der Automat N erkennt das Wort w, wenn es einen Endzustand t ∈ F gibt, der vom Startzustand q mit dem Wort w erreichbar ist:
(q, w, t) ∈ d*
Die von N erkannte Sprache ist somit
L(N) = { w ∈ A* | ∃ t ∈ F : (q, w, t) ∈ d* }
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 nichtdeterministische 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]