close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

7 Wie kann man reguläre Sprachen beschreiben (Re- guläre

EinbettenHerunterladen
7
Wie kann man reguläre Sprachen beschreiben (Reguläre Ausdrücke) III?
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. Es ist ein drittes Konzept zur Charakterisierung von regulären Sprachen neben dem DEA
mit seinen Varianten und 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
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 ist ein regulärer Ausdruck (der als Sprache die leere Menge hat).
2)
Das leere Wort ist ein regulärer Ausdruck mit der Menge als Sprache, die aus dem
leeren Wort besteht.
3)
Ein a
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 | e2
:= L1 L2 = {x | x L1 x L2} (Alternative, manchmal auch Vereinigung genannt und manchmal auch mit „+” bezeichnet):
e1e2
:= L1 L2 = {xy | x L1 y L2} (Konkatenation, manchmal auch
Produkt oder Sequenz genannt, wobei meist weggelassen wird)
e*
:= L* = {x | x L*} (Abschluss, manchmal auch Kleene'sche SternOperation oder Iteration genannt)
5)
*={ }
✄
☎
✆
✝
✟
✠
✡
✞
☛
☞
✌
✍
✎
✍
✏
✑
✒
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
✔
✕
✓
| | a1 | a2 | ... | an | AA | 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:
*
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 = e2 | e1
e1(e2 | e3) = e1e2 | e1e3
"Assoziativgesetz"
"Assoziativgesetz"
"Kommutativgesetz"10
"Distributivgesetz"
Beispiele:
1.
a*b*
= { ambn | m, n
2.
(ab)*
= {(ab)m | m
3.
(a | b)*
= {x | x
4.
(aa | ab | ba | bb)*
= {x | x
5.
Identifikatoren in Programmiersprachen:
S aA | bA | cA | ... | zA | a | b | ... | z
A aA | bA | cA | ... | zA | 0A | 1A | ... | 9A | a | b | ... | z | 0 | 1 | 2 | ... | 9
✚
✚
0}
0}
{a, b}*}
✛
✛
{a, b}* und |x| geradzahlig}
✜
✜
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
B
C
D
✣
✣
✣
✣
aB
aB | bC
aD
aD |
✤
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 auch zum
Ausdruck bringen: aa*bb*aa* .
Natürlich lässt sich schnell ein äquivalenter NEA dazu angeben:
65
Als weiteres Beispiel betrachte man den regulären Ausdruck aa*(b | c)d*. Das zugehörige Zustandübergangsdiagramm des äquivalenten NEA 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 Endlichen Automaten 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.
EA zum regulären Ausdruck 0 (1 | (23))*
✦
69
Wir wissen, dass man die -Übergänge auf der Grundlage der -Hüllenbildung aus einem
Automaten entfernen kann. Wie dies geht, soll noch einmal an diesem Beispiel verdeutlicht
werden.
✧
✧
Zur Erinnerung: Unter der -Hülle eines Zustands z versteht man die Menge H(z) aller von z
aus durch möglicherweise wiederholte -Übergänge erreichbaren Zustände einschließlich z
selbst. Man lässt den Automaten quasi die -Ü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 -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 -Übergänge aufgefasst.
✧
✧
✧
✧
✧
Jeder Sammelzustand Z wird für ein Element a des Eingabealphabets nach Nachfolgezustandsmengen untersucht. Ist z Z und ist z'
(z, a), muss auch noch H(z') zur neuen Sammelzustandsmenge hinzugenommen werden.
★
★
✩
Die Ergebnisse werden in einer Tabelle notiert.
0
[GHS]
Start
[ACDEFF'G'H'#]
Null
[ACDEFF'G'H'#]
Null
✪
[ACDD'EE'F'H'#]
Eins
✪
[A'B]
Zwei
[AB'CC'DEE'F'H'#]
Drei
1
✪
3
✪
✪
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
✪
✪
✪
2
[ACDD'EE'F'H'#]
Eins
✪
✪
[ABCC'DEE'F'H'#]
Drei
✪
[A'B]
Zwei
✪
In kursiver Schrift sind Namen mit mehr Semantik eingetragen. So bedeutet z.B. „Eins“ dass
„1 gesehen“ wurde. Die folgende Abbildung zeigt das äquivalente -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 -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
Automaten 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
S
B
C
C
✮
✮
✮
✮
✮
aS
aB
bC
aC
a
1. Schritt: " " 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
✯
(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 =
2.
1
✱
|
✱
| ... |
2
✱
m
|
j
✲
Xj |
✲
Xk | ... |
k
✲
l
Xl
Umschreiben zur Suche nach rekursiven Symbolen
Xn =
✳
i
Xn |
✴
n
| ...
Irgendeines mit dieser Eigenschaft wird ausgewählt. Die Lösung dafür ist von der Form:
Xn = 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 wiederholen, bis alle Gleichungen gelöst sind.
Den Beweis, dass damit der ä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 a <R1>
<R2> c
✶
✶
<R1>
<R2>
✶
✶
b <R1>
d <R3>
<R1>
<R3>
✶
✶
<R2>
f <R3> |
✷
Wie man unschwer sieht, geschieht die Umformung nach dem Prinzip:
Sequenz:
Iteration:
Alternative:
Terminal und einen "Rest"
durch rekursives Symbol
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
8
Wie verhalten sich reguläre Sprachen zueinander?
Nehmen wir an, es wird uns eine Sprache M
vorgegeben, die über ein Mengenprädikat P
definiert wird, also M = {x | P(x)}. Gesucht ist eine Grammatik für M. Wenn wir zu M eine
reguläre Grammatik gefunden haben, ist das Problem gelöst. Gibt es ein Kriterium, mit dem wir
entscheiden können, ob überhaupt Chancen bestehen oder ob es grundsätzlich keine reguläre
Grammatik dafür gibt? Wir suchen also nach notwendigen Eigenschaften, die alle regulären
Sprachen haben müssen. Hat eine Sprache nicht diese Eigenschaft, kann sie nicht regulär sein.
✸
✹
Ein Ansatz zum Finden eines solchen Kriteriums ist die Einsicht, dass Endliche Automaten
wegen der endlichen Zahl ihrer Zustände ein „endliches Gedächtnis” haben. Bei Eingaben, die
eine gewisse Größe überschreiten, können Wiederholungen nicht mehr von einander unterschieden werden.
Satz: („Pumping-Lemma” für reguläre Sprachen)
Sei M eine reguläre Sprache. Dann gibt ein n
, so dass sich jedes
drei Teile zerlegen lässt, dass gilt: = uvw mit |v| 1, |uv| n und ( i
✺
✻
✼
✾
✼
✿
❀
❁
✽
M mit | | n so in
0)(uviw M).
✼
✾
❂
Beweis(-ideen):
(1. Variante) Für M gibt es einen DEA A mit L(A) = M. Sei n die Zahl der Zustände von A
und x1x2...xm L(A) mit m n. Bei der Abarbeitung von x wird die Zustandsfolge z0z1z2...zm durchlaufen, wenn z0 der Startzustand ist. Dabei gibt es notwendigerweise einen Zustand, der bei der Abarbeitung mindestens zweimal erreicht
wird, also zj = zk mit 0 j < k n. Wir setzen nun u = x1x2...xj, v = xj+1xj+2...xk
und w = xk+1xk+2...xm.
❂
❁
❃
❃
Es gilt |v| 1, da k > j und |uv| n, da k n. Damit sind die ersten beiden
Anforderungen erfüllt. Da *(zj, v) = zk = zj, gilt auch *(zj, vv) = zk = zj. Also
kann v beliebig oft iteriert werden und uviw M
❁
❃
❃
❄
❄
❂
(2. Variante): Zu M gibt es eine Grammatik G mit L(G) = M. Wenn n genügend groß ist, muss
bei der Ableitung von mindestens ein Nichtterminal wiederholt auftreten, also
S j uY k-j+1 uvY m-k+1 uvw, mit j, k und m wie oben. Statt die "Y * w"Alternative gleich zu nehmen, kann man die "Y * vY"-Alternative iterieren.
Also gilt auch S * uviw.
❅
❆
❆
❆
❆
❆
❆
Beispielsweise ist {anbm | n, m
❈
❇
0} regulär, {anbn | n
❈
0} hingegen nicht.
Die Pumping-Lemma-Eigenschaft ist nicht hinreichend. Es gibt Sprachen mit diesen Eigenschaften, die aber nicht regulär sind.
75
Um die Frage beantworten zu können, ob eine vorgelegte Sprache regulär ist, kann man ggf.
folgende Beziehungen verwenden:
Satz:
Sei ein Alphabet und L, L1, L2
* seien reguläre Sprachen. Dann sind die folgenden
Sprachen auch regulär: L1 L2 (Vereinigung), L1 \ L2 (Differenz), * \ L (Komplement), L1
L2 (Durchschnitt), L1 L2 (Konkatenation), L*, LR (Spiegelsprache).
❉
❊
❉
❉
❋
❍
Beweis:
76
●
Bei der Einführung des Grammatikbegriffs wurde bereits das Wortproblem erwähnt. Es ist die
Frage nach der Existenz eines Algorithmus, der bei der Vorlage einer Zeichenkette w und einer
Grammatik G entscheiden kann, ob w L(G) ist. Bei regulären Sprachen ist das Problem:
■
„Gegeben eine reguläre Sprache L
❏
❑
* und w
■
❑
*. Ist w
■
L?”
stets mit „ja” oder mit „nein” zu entscheiden. (L sei mittels einer der drei Möglichkeiten zur
Charakterisierung regulärer Sprachen definiert.)
Gleiches gilt für das
- Leerheitsproblem: ob der Automat für L überhaupt ein Wort akzeptiert / die Grammatik
für L ein Wort generiert
- Endlichkeitsproblem: ob der Automat für L unendlich viele Wörter akzeptiert / die
Grammatik für L unendlich viele Wörter generiert
- Durchschnittsproblem: ob die jeweiligen Automaten für zwei reguläre Sprachen
mindestens ein gemeinsames Wort erkennen
- Äquivalenzproblem: ob zwei Automaten die gleiche Sprache erkennen.
77
Document
Kategorie
Seele and Geist
Seitenansichten
22
Dateigröße
207 KB
Tags
1/--Seiten
melden