close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

6 Wie kann man reguläre Sprachen noch beschreiben (Endliche

EinbettenHerunterladen
6
Wie kann man reguläre Sprachen noch beschreiben
(Endliche Automaten)?
Bislang geschah die Charakterisierung von Sprachen durch „generative Kalküle”, also bei
Typ-2-Sprachen durch kontextfreie Grammatiken, EBNF und Syntaxgraphen. Wir führen nun
den endlichen Automaten als ein neues Hilfsmittel zur Beschreibung regulärer Sprachen ein,
also solche, die durch einseitig lineare Grammatiken charakterisiert werden können. Damit
gelangen wir zu einem „analysierenden Kalkül”, zu einem Sprachakzeptor.
Wir werden weiter sehen, dass die endlichen Automaten in der Informatik in vielen Bereichen
auftreten und von großer praktischer Bedeutung sind.
Das Grundprinzip ist simpel. Betrachten wir folgende normierte einfache reguläre Grammatik
G:
S 6 aB
B 6 aB | bC
C 6 aD | bC
D 6 aD | g
und „malen” - nach John Myhill (1957) - einmal in einem „Produktionenanwendungsreihenfolgediagramm” - das wir später aus gutem Grund auch Zustandsübergangs- /Transitions-Diagramm
(oder kürzer „Z-Diagramm”) nennen werden - die Produktionen auf, um graphisch zu veranschaulichen, was sie generieren können.
Produktionenanwendungsreihenfolgediagramm /
Zustandsübergangsdiagramm
Wir können das Diagramm in analoger Weise zum Generierungsprozess bei der Grammatik
G lesen: Man startet im speziell gekennzeichneten Startzustand S, generiert ein a und geht in
einen Folgezustand B über. Von dem aus kann man wieder a's generieren, wobei man immer
wieder in den Zustand B zurückkehrt oder nach der Erzeugung eines b in einen Zustand C
kommen. Dieser erlaubt die Erzeugung weiterer b's oder eines a's, was den Übergang in den
Zustand D bewirkt. Hier kann man entweder weitere a's produzieren oder Schluss machen,
wobei man in einen Endzustand kommt, der hier mit # markiert ist.
40
Am Z-Diagramm wie auch an der Grammatik kann man sehen, dass L(G) = {aarbbsaat | r, s, t $
0} gilt. Also, die einfachen rechtslinearen Grammatiken lassen sich direkt in Z-Diagramme
umschreiben.
Achtung! Die Produktionenanwendungsreihenfolge- / Z-Diagramme nicht mit Syntaxdiagrammen verwechseln!
Die obige Sprache {aarbbsaat | r, s, t $ 0} würde auch mit der folgenden Grammatik G' erzeugt
werden:
S 6 aS | aB
B 6 bC | bB
C 6 aC | a
Sie liegt aber nicht in der Normalform in dem Sinn vor, dass es keine Produktion der Art C 6 a
geben sollte und nur höchstens eine der Art D 6 g. Zu G' gehört das folgende Diagramm:
Die Interpretation geht analog: Man kann ein a erzeugen und wieder in den Folgezustand S
zurückkehren. Oder man kann ein a erzeugen und dann in den Zustand B übergehen. Von B aus
kann man b's erzeugen und wahlweise in den Zustand B zurückkehren oder nach C gehen. Im
zweiten Fall kehrt man unter Erzeugung von a's wieder nach C zurück oder man kommt bei der
Erzeugung eines letzten a in einen ebenfalls speziell gekennzeichneten Endzustand, von dem
aus dann Schluss ist.
Produktionenanwendungsreihenfolgediagramm /
Zustandsübergangsdiagramm
Eine Beobachtung kann man bereits an dieser Stelle machen: Das Z-Diagramm von G' hat
weniger Zustände als das von G.
41
Man kann sich leicht überlegen, dass man zu jedem Z-Diagramm einer Grammatik ein ZDiagramm konstruieren kann, das genau einen Pfeil mit einer g-Markierung hat, der in einen
einzigen Endzustand geht. Dabei denke man an den analogen Beweis für Grammatiken.
Jetzt kommt der Übergang vom generierenden zum analysierenden Kalkül: Dabei stellen wir
uns einen Mechanismus (= endlicher Automat) vor, bei dem auf einem Eingabeband eine
Zeichenkette geschrieben werden kann und der außerdem einen Lesekopf besitzt, der von links
nach rechts sukzessive die Eingabe liest. Dabei kann er auch auf ein intern gespeichertes
Zustandsübergangsdiagramm zugreifen, es lesen und interpretieren.
Immer dann, wenn der Automat in einem (aktuellen) Zustand z ist, auf dem Eingabeband ein
Zeichen c gelesen wird und dieses Zeichen an einem ausgehenden Pfeil vom Zustand nach
einem Folgezustand z' des Diagramms steht, geht der Lesekopf um eine Position weiter und der
aktuelle Zustand wird z'. Falls kein geeignet beschrifteter Pfeil zur Verfügung steht, bleibt der
Automat stehen und signalisiert einen Fehler. Ansonsten „akzeptiert” / „erkennt” der Automat
die Eingabe.
Eine solche Konfiguration sei folgendermaßen aufgebaut:
Beispiel eines endlichen erkennenden (nichtdeterministischen) Automaten
Der Automat erkennt oder akzeptiert ein Wort gdw. der Lesekopf das gesamte Eingabewort
gelesen hat und man von Startzustand beginnend und den Pfeilen nachgehend, die mit dem
aktuellen Eingabezeichen beschriftet sind, schließlich den / einen Endzustand erreicht.
42
Wie man aber sieht, gibt es z.B. im Zustand B zwei ausgehende Pfeile mit gleicher Beschriftung b, denen man nachgehen kann. Eine solche Situation bezeichnet man als nichtdeterministisch. Das Akzeptieren/Erkennen eines Wortes w durch den Automaten wird in dem
Sinne erweitert, dass nur gefordert wird, dass es einen Pfad durch das Z-Diagramm gibt, beim
Startzustand beginnend und beim Endzustand aufhörend, den der Automat bei der Abarbeitung
von w nehmen kann.
Wie würde man eine Produktion der Art A 6 B in einem Z-Diagramm darstellen? Ganz
einfach, nämlich in Analogie zu A 6 gB, also durch einen mit g markierten Pfeil vom Zustand
A nach B.
Wegen der analysierenden Eigenschaften werden diese Automaten auch als endliche erkennende Automaten bezeichnet. In den Darstellungen, die man in der Literatur findet, gibt es viele
Varianten, die mit der Interpretation der graphischen Zeichen im folgenden angegeben sind.
Graphische Primitive für Zustandsübergangsdiagramme
Hinweis: Sich nicht verzweigende Ketten von Zustandsübergängen schreibt man bei Verwendung der Automaten in der Praxis der Einfachheit halber als einen einzigen Übergang wie x =
x1x2 ... xn in der Abbildung (was analog ist zu einer Produktion A 6 x1x2 ... xnB).
Endliche Automaten verwendet man häufig zum Modellieren von Abläufen von Prozessen
(„Getränkeautomat”, Interaktionsdiagramme, usw.)
43
Für ein tieferes Verständnis müssen wir das Konzept des endlichen Automaten präzise
definieren und beginnen zunächst mit dem einfachsten Fall:
Definition:
Ein deterministischer endlicher Automat (DEA) M ist gegeben durch ein 5-Tupel (Z, Σ, δ, s,
E), wobei Z die (endliche) Menge der Zustände ist, Σ ist das Eingabealphabet, δ : Z×Σ 6 Z ist
eine (partielle) Abbildung, die Zustandsüberführungsfunktion, s 0 Z ein spezieller Startzustand
und E f Z die Menge der Endzustände.
δ muss nicht für alle Paare aus (z, a) 0 Z×Σ definiert sein („partielle Abbildung”). Ist dies der
Fall, heißt M vollständig.
Ê
Da δ eine Funktion ist, gibt es höchstens einen Nachfolgezustand, deshalb die Bezeichnung
„deterministisch”.
Die Funktion δ lässt sich anschaulich durch die Z-Diagramme beschreiben. Ein δ((A, a)) = B,
wobei man die Doppelklammerung meist weglässt und kürzer δ(A, a) = B schreibt, kann
dargestellt werden durch zwei Kreise mit einem Verbindungspfeil. Im Kreis am Pfeilbeginn
steht A, im Kreis am Pfeilende steht B und der Pfeil selbst ist mit a beschriftet.
Letztlich steht δ(A, a) = B für die Produktion A 6 aB. Zustände werden also zu Nichtterminalen und umgekehrt.
Man kann auch Tabellen verwenden und δ(z0, a) = z0, δ(z0, b) = z1, δ(z1, a) = z0, ... übersichtlicher schreiben:
δ
a
b
z0
z0
z1
z1
z0
z3
...
...
Die Verhaltensweise eines Automaten, also die Erkennung eines Wortes, muss ebenfalls noch
präzisiert werden. So kommen wir zur erweiterten Zustandsüberführungsfunktion δ* : Z×Σ* 6
Z des Automaten M, mit
δ*(z, g) = z, für alle z 0 Z
δ*(z, aw) = δ*(δ(z, a), w), für a 0 Σ, w 0 Σ*
44
δ* beschreibt die schrittweise Abarbeitung eines Wortes w auf dem Eingabeband. Wenn M in
einem Zustand z ist, a auf der aktuellen Eingabeposition steht, aber kein δ(z, a) definiert ist,
bricht δ* ab.
Für eine Präzisierung dieses Abarbeitungsvorgangs benötigt man noch weitere Begriffe:
Definition:
Eine Konfiguration k ist ein Paar k = (z, v), wobei z 0 Z der aktuelle Zustand ist und v 0 Σ*
das noch zu verarbeitende Restwort auf dem Eingabeband.
Das Paar k' = (z', w) heißt Folgekonfiguration von k, i. W. k | k', wenn v = aw mit w 0 Σ* ist
und z' = δ(z, a).
Ein Automat M = (Z, Σ, δ, z0, E) erkennt / akzeptiert ein Wort a1a2...an 0 Σ*, wenn es eine
Folge von Konfigurationen (z0, a1a2...an) | (z1, a2...an) | ... | (zn, g) gibt mit zn 0 E und für 0 # i
< n gilt δ(zi, ai+1) = zi+1.
Ê
Anmerkung: Der Ableitungsprozess bei rechtslinearen Grammatiken, der sich als reflexive,
transitive Hülle Y* der Ableitungsrelation Y auffassen lässt, spiegelt sich wieder in der reflexiven transitiven Hülle |* der Relation | über den Konfigurationen bei endlichen Automaten,
wobei |* so definiert ist:
k |* k für alle Konfigurationen k 0 K
k |* k'', falls es ein k' 0 K gibt mit k | k' und k' |* k''
Definition:
Sei M = (Z, Σ, δ, z0, E) ein endlicher Automat. Dann ist die von M akzeptierte Sprache die
Menge L(M) = {w | w 0 Σ*, (z0, w) |* (z, g), z 0 E}.
Zwei endliche Automaten M und M' heißen äquivalent, wenn L(M) = L(M') ist.
Ê
Da δ*(z, w) = z' gdw. (z, w) |* (z', g) gilt, ist leicht einzusehen, dass zu obiger Definition
äquivalent ist:
L(M) = {w | w 0 Σ*, δ*(z0, w) = z, z 0 E}
45
Wir können an dieser Stelle die folgende Feststellung machen:
Satz:
Zu jedem deterministischen endlichen Automaten M = (Z, Σ, δ, z0, E) gibt es eine reguläre
Grammatik G = (V, G, P, z0) mit L(M) = L(G).
Beweis:
Jeder Zustand des Automaten M wird zu einem Nichtterminal der rechtslinearen Grammatik
G, also Z = V. Gibt es einen Übergang δ(z, a) = z', gilt z 6 az' 0 P. Falls z' Endzustand ist, kann
man entweder statt z 6 az' nur die Produktion z 6 a hinzunehmen oder zusätzlich z' 6 g.
Dass alles, was M erkennt auch von G produziert werden kann und umgekehrt, dass alles, was
G produziert auch von M erkannt werden kann, ist wegen der Konstruktion von P aus δ unmittelbar klar.
Ê
Allerdings muss an dieser Stelle auch darauf hingewiesen werden, dass die Definition des
endlichen Automaten weder mit dem Z-Diagramm für die Grammatik
S 6 aS | aB
B 6 bC | bB
C 6 aC | a
noch mit dem für die Grammatik
S 6 aB
B 6 aB | bC
C 6 bC | aD
D 6 aD | g
in den Eingangsbeispielen kompatibel ist. Im ersten Fall starten zwei Pfeile mit der Beschriftung
b in B und gehen nach B bzw. C. Hier liegt ein nichtdeterministisches Verhalten vor. Um das zu
modellieren, bräuchten wir eine Verallgemeinerung von δ, was die Angabe δ(B, b) = B und δ(B,
b) = C zum Ausdruck bringen würde. Dies könnte mit der Angabe δ(B, b) = {B, C} geschehen.
Im zweiten Fall gibt es einen g-Übergang, der, wie wir noch sehen werden, im allgemeinen
Fall - also nicht gerade vor dem Übergang in den Endzustand - auch einen Nichtdeterminismus
darstellt.
Es wird sich zeigen, dass die genannten Probleme gelöst werden können, wobei wir noch
weitere Definitionen benötigen.
46
Definition:
Ein nichtdeterministischer endlicher Automat (NEA) ist ein 5-Tupel (Z, Σ, δ, s, E). Z , Σ, s und
E sind - wie beim DEA - die Menge der Zustände, das Eingabealphabet, der Startzustand9 bzw.
die Menge der Endzustände. Die Übergangsfunktion δ wird erweitert zu δ : Z × Σ 6 (Z), wobei
(Z) die Potenzmenge von Z ist.
Die erweiterte Übergangsfunktion δ* des NEA wird definiert als:
δ*(z, g) = {z}, für alle z 0 Z
δ*(z, aw) = ^z'0δ(z, a) δ*(z', w), für a 0 Σ, w 0 Σ*
Der Konfigurationsbegriff überträgt sich direkt.
Das Paar k' = (z', w) heißt Folgekonfiguration von k, i. W. k | k', wenn v = aw mit w 0 Σ* ist
und z' 0 δ(z, a).
Ein Automat M = (Z, Σ, δ, z0, E) erkennt / akzeptiert ein Wort a1a2...an 0 Σ*, wenn es eine
Folge von Konfigurationen (z0, a1a2...an) | (z1, a2...an) | ... | (zn, g) gibt mit zn 0 E und für 0 # i
< n gilt zi+1 0 δ(zi, ai+1).
Sei M = (Z, Σ, δ, z0, E) ein NEA. Dann ist die von M akzeptierte Sprache die Menge L(M) =
{w | w 0 Σ*, (z0, w) |* (z, g), z 0 E}.
Ê
Man sieht sofort, dass ein DEA auch als NEA aufgefasst werden kann. Dabei ist nur notwendig zu erkennen, dass beim DEA die Mächtigkeit der Menge der Nachfolger 1 ist. Also kann
man sagen, dass es zu jedem DEA auch einen äquivalenten NEA gibt. Die Frage ist, ob auch die
Umkehrung gilt.
9
In manchen Büchern wird der NEA über eine Menge von Anfangszuständen definiert.
Dementsprechend muss auch δ modifiziert werden.
47
Satz (Rabin, Scott 1959):
Zu jedem NEA gibt es einen äquivalenten DEA, also L(NEA) = L(DEA).
Beweisidee:
Sei M = (Z, Σ, δ, s, E) ein NEA. Aus ihm konstruieren wir quasi durch „Parallelverfolgung”
der Nachfolgezustände an den jeweiligen Zuständen den DEA N = ((Z), Σ, δN, s, EN). Die
Menge der Nachfolgerzustände jeweils zu einem a 0 Σ ergibt einen einzigen „Sammelzustand”
für N. Die Menge der Endzustände von N sind die Zustandsmengen, die ein Element aus E
beinhalten. Genauer gesagt gilt schließlich
δN(X, a) = ^z0X δ(z, a) für alle X f Z
EN = {Y f Z | Y 1 E … i}
Durch Induktion lässt sich nun zeigen dass für alle w 0 Σ* gilt: δ*(s, w) = δN*({s}, w).
Ê
Weil die Menge aller möglichen Zustände von N die Menge aller Teilmengen von Z ist, nennt
man diese Konstruktion auch die „Potenzmengenkonstruktion”. Es sei gleich an dieser Stelle
gesagt, dass nicht unbedingt alle Elemente von (Z) im so konstruierten Automaten letztlich
notwendig sind. Dazu siehe auch folgendes Beispiel:
Beispiel:
Betrachte folgenden NEA:
Nichtdeterministischer endlicher Automat
48
Der Automat hat die folgende Tabellendarstellung mit B als Endzustand, was durch Unterstreichung kenntlich gemacht wurde:
M
a
b
c
A
{A, B}
{A}
{A}
B
{B}
{A}
{A, B}
So ergeben sich z.B. beim Übergang a im Startzustand A die Folgezustände A und B, die im
Sammelfolgezustand [AB] notiert werden. Jeder Zustand dieses Sammelzustands wird untersucht und seine möglichen Folgezustände hinsichtlich eines Eingabezeichens werden wieder in
einem Sammelzustand zusammengefasst. Schließlich ergibt sich der folgende Automat mit den
Endzuständen [AB] und [B].
N
a
b
c
[A]
[AB]
[A]
[A]
[AB]
[AB]
[A]
[AB]
[B]
[B]
[A]
[AB]
Äquivalenter deterministischer endlicher Automat
Im Zustandsübergangsdiagramm ist gut ersichtlich, dass der neue Zustand [B] vom Startzustand aus nicht erreichbar und somit überflüssig ist. Damit kann man den Automaten um
diesen Zustand reduzieren.
49
Auf den formalen Beweis, dass mit den Konstruktionen tatsächlich ein äquivalenter Automat
entsteht, wird an dieser Stelle verzichtet.
Ê
Den Nichtdeterminismus sollte man nicht als Erschwernis sehen. Er kann sehr hilfreich bei der
Konstruktion von endlichen Automaten sein.
Beispiel:
Betrachten wir die Sprache, die aus allen Wörtern aus {0, 1}* bestehen, die auf 100 enden.
Ein zugehöriger NEA ist schnell konstruiert:
Ihn gleich in der deterministischen Variante hinzuschreiben, ist zweifelsohne aufwendiger. Es
empfiehlt sich, erst den zugehörigen NEA zu konzipieren und ihn dann zum äquivalenten DEA
zu transformieren („separation of concerns”):
50
Document
Kategorie
Gesundheitswesen
Seitenansichten
11
Dateigröße
198 KB
Tags
1/--Seiten
melden