close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

7 Wie kann man reguläre Sprachen noch beschreiben (Reguläre

EinbettenHerunterladen
7
Wie kann man reguläre Sprachen noch beschreiben
(Reguläre Ausdrücke)?
So wie die EBNF im Vergleich zu den kontextfreien Grammatiken den Umgang mit kontextfreien Sprachen erleichtert, vereinfachen reguläre Ausdrücke oft die Arbeit mit regulären Sprachen. Sie sind ist ein drittes Konzept zur Charakterisierung von regulären Sprachen neben dem
DEA mit seinen Varianten und den einseitig linearen Grammatiken. Diese neue Charakterisierung gleicht mehr der Beschreibung von Sprachen durch Mengen mit bereits bekannten, auf
Mengen definierten Operationen.
Ausgehend vom einem Alphabet Σ bei dem jedes Element a 0 Σ die Sprache {a} repräsentiert,
werden drei Operatoren eingeführt, um komplexere Zeichenkettenmengen zu definieren: Konkatenation, Alternative, Abschluss.
Definition:
Reguläre Ausdrücke werden rekursiv definiert.
1)
Die leere Menge i ist ein regulärer Ausdruck (der als Sprache die leere Menge hat).
2)
Das leere Wort g ist ein regulärer Ausdruck mit der Menge als Sprache, die aus dem
leeren Wort besteht.
3)
Ein a 0 Σ ist ein regulärer Ausdruck mit {a} als Sprache.
4)
Sind e, e1 und e2 reguläre Ausdrücke mit den zugehörigen Sprachen L, L1 bzw. L2, dann
sind die folgenden Ausdrücke auch reguläre Ausdrücke mit den assoziierten Sprachen:
(e)
:= L (d.h. einfach, man darf Klammern setzen)
e1 | e 2
:= L1 c L2 = {x | x 0 L1 w x 0 L2} (Alternative, manchmal auch Vereinigung genannt und manchmal auch mit „+” bezeichnet):
e 1e 2
:= L1 B L2 = {xy | x 0 L1 v y 0 L2} (Konkatenation, manchmal auch
Produkt oder Sequenz genannt, wobei B meist weggelassen wird)
e*
:= L* = {x | x 0 L*} (Abschluss, manchmal auch Kleene'sche SternOperation oder Iteration genannt)
5)
i* = {g}
Ê
Bemerkungen:
Der syntaktische Teil der obigen Definition für reguläre Ausdrücke A über einem Alphabet Σ
= {a1, a2, ..., an} ließe sich auch kurz mit
A 6 i | g | a1 | a2 | ... | an | AA | A+A | A* | (A)
notieren.
Die Syntax regulärer Ausdrücke darf nicht mit der EBNF verwechselt werden. Z.B. fehlt bzgl.
der EBNF die Option "[ ]", die auch gestattet, keine der Alternativen zu wählen. Das "|" verlangt
mindestens eine Alternative. Außerdem verwendet die EBNF Nichtterminale.
Ê
63
Prioritätsregeln machen die regulären Ausdrücke einfacher:
*
B
|
höchste Priorität
mittlere Priorität
unterste Priorität,
also ist ((p) | ((p)(q))) kürzer durch p | pq darstellbar.
Mit regulären Ausdrücken lässt sich auch "rechnen". Z.B. gelten folgende Regeln:
(e1e2)e3 = e1(e2e3)
(e1 | e2) | e3 = e1 | (e2 | e3)
e1 | e2 = e 2 | e 1
e1(e2 | e3) = e1e2 | e1e3
"Assoziativgesetz"
"Assoziativgesetz"
"Kommutativgesetz"10
"Distributivgesetz"
Beispiele:
1.
a*b*
= { ambn | m, n $ 0}
2.
(ab)*
= {(ab)m | m $ 0}
3.
(a | b)*
= {x | x 0 {a, b}*}
4.
(aa | ab | ba | bb)*
= {x | x 0 {a, b}* und |x| geradzahlig}
5.
Identifikatoren in Programmiersprachen:
S 6 aA | bA | cA | ... | zA | a | b | ... | z
A 6 aA | bA | cA | ... | zA | 0A | 1A | ... | 9A | a | b | ... | z | 0 | 1 | 2 | ... | 9
Einfacher zu beschreiben durch den regulären Ausdruck:
(a | b | c | ... | z) ( a | b | c | ... | z | 0 | 1 | ... | 9 )*
Ê
10
Natürlich gilt ab … ba .
64
Betrachte die folgende Grammatik:
S 6 a S | aB
B 6 bB | bC
C 6 aC | a
Der Sachverhalt, den sie beschreibt, ist schlicht folgender: „Betrachte Zeichenketten, die mit
einem oder mehreren a's beginnen, gefolgt von einem oder mehreren b's, auf die dann wieder ein
oder mehrere a's folgen.”
Dies lässt sich viel eleganter durch einen zu ihr äquivalenten regulären Ausdruck darstellen:
aa*bb*aa* .
Natürlich lässt sich schnell ein äquivalenter NEA dazu angeben, wobei es am einfachsten ist,
von der Grammatik auszugehen, wenn sie schon wie hier in einfacher Form vorliegt:
65
Als weiteres Beispiel betrachte man den regulären Ausdruck aa*(b | c)d*. Das zugehörige Zustandübergangsdiagramm des äquivalenten NEAg hat folgende Gestalt.
Die vorangegangenen Beispiele haben bereits Hinweise gegeben, dass es sich bei den Endlichen Automaten mit ihren Varianten, den einseitig linearen Grammatiken und den hier behandelten regulären Ausdrücken um äquivalente Konzepte zur Beschreibung regulärer Sprachen
handelt. Während es nicht ganz so leicht ist, aus einer vorgegebenen Grammatik den regulären
Ausdruck systematisch zu generieren, ist es vergleichweise einfach, zu einem regulären Ausdruck einen äquivalenten NEAg zu konstruieren.
66
Dazu baut man sukzessive aus den Bestandteilen des regulären Ausdrucks quasi von „innen
nach außen” den Automaten auf:
Automat zur Alternative (r1 | r2)
Automat zur Konkatenation r1 r2
67
Automat zur Iteration r*
Automat zum Terminalsymbol t
Startgraph
68
Beispiel:
Betrachten wir den regulären Ausdruck 0 (1 | (23))*. Eine syntaktische Analyse, die man am
besten durch einen Syntaxbaum darstellt, ergibt, dass es sich um eine Sequenz einer Iteration
einer Alternative handelt, die aus einem „elementaren” Terminalsymbol 1 und einer Sequenz
zweier Terminalsymbole 2 bzw. 3 besteht. Im u.a. Automaten erfolgt die Erkennung von 2 in
einem Zustand A, die von 3 in B. Die Sequenz aus 2 und 3 braucht wegen der Systematik einen
Zustand C. 1 korrespondiert zu D, die Alternative ...|... zu E, die Iteration (...)* zu F, 0 zu G und
schließlich die Komposition äußere Sequenz zu H.
NEAg zum regulären Ausdruck 0 (1 | (23))*
69
Wir wissen, dass man die g-Übergänge auf der Grundlage der g-Hüllenbildung aus einem
Automaten entfernen kann. Wie dies geht, soll noch einmal an diesem Beispiel verdeutlicht
werden.
Zur Erinnerung: Unter der g-Hülle eines Zustands z versteht man die Menge H(z) aller von z
aus durch möglicherweise wiederholte g-Übergänge erreichbaren Zustände einschließlich z
selbst. Man lässt den Automaten quasi die g-Übergänge „weiterticken“, bis er bei „echten“
Eingabesymbolen Halt macht und sammelt die dabei erreichten Zustände in einer Menge auf.
Wie aus dem Beispiel ersichtlich, ist z.B. die g-Hülle von S die Zustandsmenge {S, G, H}, die
man gewöhnlich durch [SGH] (oder durch eine Permutation wie [GHS]) notiert. Ein solcher
„Sammelzustand“ wird als neuer Zustand des zu konstruierenden äquivalenten endlichen
Automaten ohne g-Übergänge aufgefasst.
Jeder Sammelzustand Z wird für ein Element a des Eingabealphabets nach Nachfolgezustandsmengen untersucht. Ist z 0 Z und ist z' 0 δ(z, a), muss auch noch H(z') zur neuen Sammelzustandsmenge hinzugenommen werden.
Die Ergebnisse werden in einer Tabelle notiert.
0
1
2
3
[ACDEFF'G'H'#]
Null
i
i
i
[ACDEFF'G'H'#]
Null
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[ACDD'EE'F'H'#]
Eins
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[A'B]
Zwei
i
i
i
[ABCC'DEE'F'H'#]
Drei
[AB'CC'DEE'F'H'#]
Drei
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[GHS]
Start
In kursiver Schrift sind Namen mit mehr Semantik eingetragen. So bedeutet z.B. „Eins“ dass
„1 gesehen“ wurde. Die folgende Abbildung zeigt das äquivalente g-freie Zustandsübergangsdiagramm. Sammelzustände, die einen ursprünglichen erkennenden Zustand beinhalten, werden
zu neuen erkennenden Sammelzuständen.
70
Das Verfahren liefert uns den folgenden einfacheren Automaten:
Die g-freie Version des Automaten für den regulären Ausdruck
0(1| 23)*
aus dem man den folgenden Minimalautomat konstruieren kann:
Ê
71
Es wurde bereits gesagt, dass die Konstruktion des zu einer regulären Grammatik äquivalenten
regulären Ausdrucks nicht ganz einfach ist. Hier soll die allgemeine Beziehung behandelt
werden:
Satz:
Zu jeder regulären Grammatik gibt es einen regulären Ausdruck, der dieselbe Sprache definiert.
Beweis(idee) durch Beispiel:
S 6 aS
S 6 aB
B 6 bC
C 6 aC
C6a
1. Schritt: "6" wird zu "=". Dann entsteht ein "Gleichungssystem"
S = aS | aB
B = bC
C = aC | a
2. Schritt: Die Gleichungen werden gelöst. Die Nichtterminale, die durch sich selbst definiert
sind, werden zuerst behandelt. Die Gleichung für C hat (vermutlich) die Lösung C = a*a, daraus
folgt der Ausdruck a*a = aa*a | a , für den die Gültigkeit des Gleichheitszeichens zu beweisen
ist. Dies ist leicht einzusehen, denn der reguläre Ausdruck der linken Seite steht für die Zeichenketten a, aa, aaa, ... . Der erste Teil der rechten Seite beschreibt die Zeichenketten aa, aaa, aaa,
... . Es fehlt also nur noch die Zeichenkette, die aus einem a besteht. Diese wird aber aus dem
zweiten regulären Ausdruck bestimmt. Also stimmt die geschätzte Lösung.
Eingesetzt in die anderen Gleichungen ergibt dies:
S = aS | aB
B = ba*a
7 (Lösung für B frei Haus geliefert)
Es bleibt
S = aS | aba*a
Durch analoge Überlegungen wie für C ergibt sich für S = a*aba*a
Ê
72
Allgemeines Verfahren
1.
Grammatik umschreiben in Gleichungsform:
Xi = δ1 | δ2 | ... | δm | ψjXj | ψkXk | ... | ψlXl
2.
Umschreiben zur Suche nach rekursiven Symbolen
Xn = αiXn | ψn | ...
Irgendeines mit dieser Eigenschaft wird ausgewählt. Die Lösung dafür ist von der Form:
Xn = αiαi*ψn. Gibt es kein rekursives Symbol, ist man fertig.
Xn = < was auch immer da steht >
ist Lösung
3.
Einsetzen der Lösung in alle anderen Gleichungen
2. und 3. solange wiederholen, bis alle Gleichungen gelöst sind.
Den Beweis, dass damit der zur Ausgangsgrammatik äquivalente reguläre Ausdruck konstruiert wird, schenken wir uns.
Ê
Die Umkehrung des Zusammenhangs zwischen regulären Ausdrücken und regulären Grammatiken gilt auch:
Satz:
Zu jedem regulären Ausdruck gibt es eine reguläre Grammatik.
Beweisidee durch ein Beispiel:
ab* (c | df*) lässt sich beschreiben durch die Grammatik:
S 6 a <R1>
<R2> 6 c
<R1> 6 b <R1>
<R2> 6 d <R3>
<R1> 6 <R2>
<R3> 6 f <R3> | g
Wie man unschwer sieht, geschieht die Umformung nach dem Prinzip:
Sequenz:
Iteration:
Alternative:
Terminalsymbol und einen "Rest"
durch rekursives Nichtterminal
durch |
Ê
73
Zusammenfassung:
Reguläre Ausdrücke sind nur eine andere, aber oft bequemere Form der Charakterisierung von Zeichenkettenmengen, die auch mit einseitig linearen Grammatiken
oder mit Endlichen Automaten beschreibbar sind. Die verschiedenen Darstellungen
lassen sich durch einfache Verfahren ineinander überführen.
74
Document
Kategorie
Gesundheitswesen
Seitenansichten
7
Dateigröße
428 KB
Tags
1/--Seiten
melden