close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

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

EinbettenHerunterladen
6
Wie kann man reguläre Sprachen noch beschreiben
II (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 einfache rechtslineare Grammatik G:
S
B
C
D
aB
aB | bC
aD
aD |
✁
und „malen” einmal in einem „Produktionenanwendungsreihenfolgediagramm” - das wir später
aus gutem Grund auch Zustandsübergangsdiagramm (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 Grammatiken lassen sich direkt in Z-Diagramme umschreiben.
✂
Achtung! Die Produktionenanwendungsreihenfolge- / Z-Diagramme nicht mit Syntaxdiagrammen verwechseln!
Die obige Sprache {aarbbsaat | r, s, t
werden:
S
B
C
✄
✄
✄
✂
0} würde auch mit der folgenden Grammatik G' erzeugt
aS | aB
bC | bB
aC | a
Sie liegt aber nicht in der Normalform in dem Sinn vor, dass es keine Produktion der Art C
geben sollte und nur höchstens eine der Art D
. Zu G' gehört das folgende Diagramm:
✄
✄
a
☎
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 -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 B in einem Z-Diagramm darstellen? Ganz
einfach, nämlich in Analogie zu A
B, also durch einen mit 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.
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 M ist gegeben durch ein 5-Tupel (Z, , , s, E),
wobei Z die (endliche) Menge der Zustände ist, ist das Eingabealphabet, : Z ×
Z ist
eine (partielle) Abbildung, die Zustandsüberführungsfunktion, s Z ein spezieller Startzustand
und E Z die Menge der Endzustände.
✟
✠
✡
✠
✡
☛
☞
✌
muss nicht für alle Paare aus (z, a)
der Fall, heißt M vollständig.
✍
Z×
✎
✏
definiert sein („partielle Abbildung”). Ist dies
✑
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
len und umgekehrt.
✒
aB. Zustände werden also zu Nichttermina✓
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 × *
Z des Automaten M, mit
✒
✓
*(z, ) = z, für alle z Z
*(z, aw) = *( (z, a), w), für a
✕
✒
✒
✒
✖
✒
✖
✔
,w
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 Z der aktuelle Zustand ist und v
das noch zu verarbeitende Restwort auf dem Eingabeband.
✘
Das Paar k' = (z', w) heißt Folgekonfiguration von k, i. W. k
und z' = (z, a).
✚
k', wenn v = aw mit w
✛
✜
✘
*
✙
* ist
✢
Ein Automat M = (Z, , , z0, E) erkennt / akzeptiert ein Wort a1a2...an
*, wenn es eine
Folge von Konfigurationen (z0, a1a2...an) (z1, a2...an) ... (zn, ) gibt mit zn 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 * der Ableitungsrelation
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 K
k * k'', falls es ein k' 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
*, (z0, w) * (z, ), z E}.
✬
✭
✬
✫
✪
✮
✫
Zwei endliche Automaten M und M' heißen äquivalent, wenn L(M) = L(M') ist.
✯
Da *(z, w) = z' gdw. (z, w) * (z', ) gilt, ist leicht einzusehen, dass zu obiger Definition
äquivalent ist:
✭
✪
L(M) = {w | w
✫
✬
✮
*, *(z0, w) = z, z
✭
✫
E}
45
Document
Kategorie
Gesundheitswesen
Seitenansichten
9
Dateigröße
118 KB
Tags
1/--Seiten
melden