Grundlagen der Theoretischen Informatik Reguläre Ausdrücke und

1
2
Reguläre Ausdrücke und reguläre Sprachen
Grundlagen der
Theoretischen Informatik
Satz: [Kleene]
Die Klasse der durch reguläre Ausdrücke beschreibbaren Sprachen
ist genau die Klasse der regulären Sprachen.
Till Mossakowski
Beweis: Dass es für jede Sprache, die durch einen regulären
Ausdruck beschrieben werden kann, stets einen endlichen
Automaten gibt, der die Sprache akzeptiert, folgt aus der
Beobachtung, dass 0/ und {a} für beliebiges a ∈ Σ von endlichen
Automaten akzeptierte Sprachen sind und dem Satz über die
Abschlusseigenschaften der von endlichen Automaten akzeptierten
Sprachen.
Fakultät für Informatik
Otto-von-Guericke Universität
Magdeburg
Wintersemester 2014/15
3
Wir müssen also noch zeigen, dass es für jede Sprache L, die von
einem endlichen Automaten akzeptiert wird, einen regulären
Ausdruck α gibt mit L(α) = L.
4
Wir zeigen durch Induktion über k, dass alle R(i, j, k) durch einen
regulären Ausdruck beschreibbar sind.
Sei M = (K, Σ, ∆, s, F) ein endlicher Automat mit K = {q1 , . . . , qn }
und sei s = q1 . Für i, j = 1, . . . , n und k = 0, 1, . . . , n definieren wir
Induktionsverankerung: Sei k = 0. Dann gilt
i 6= j :
R(i, j, k) = {w ∈ Σ∗ | M geht unter w von qi nach qj
über, d.h., (qi , w) `∗M (qj , ε), ohne dass
einer der Zwischenzustände ein Zustand
in {qk+1 , . . . , qn } ist. Anfangs- und
Schlusszustand der Berechnung“
”
zählen hierbei nicht als Zwischenzustände.}
i=j :
R(i, j, 0) = {a ∈ Σ ∪ {ε} | (qi , a, qj ) ∈ ∆}
R(i, j, 0) = {a ∈ Σ ∪ {ε} | (qi , a, qj ) ∈ ∆} ∪ {ε}
R(i, j, 0) ist also für alle i, j = 1, . . . , n endlich und somit eine durch
einen regulären Ausdruck beschreibbare Sprache!
5
6
Von endlichen Automaten
zu regulären Ausdrücken durch
Elimination von Zuständen
Induktionsschritt: Nehmen wir also an, dass die R(i, j, l) durch
einen regulären Ausdruck beschreibbar sind für l = 0, . . . , k und alle
i, j = 1, . . . , n. Da
R(i, j, k + 1) = R(i, j, k) ∪ R(i, k + 1, k)R(k + 1, k + 1, k)∗ R(k + 1, j, k)
c
ist jedes R(i, j, k + 1) durch einen regulären Ausdruck beschreibbar.
b
q0
Der Satz folgt nun aus
L(M) =
[
a
q1
q2
q0
ε ∪ bc∗ a
q2
ε
R(1, j, n)
j | qj ∈F
Wir verallgemeinern Zustandsgraphen und beschriften die Kanten
mit regulären Ausdrücken.
Dabei setzen wir ε := 0/ ∗ , d.h. L(ε) = L(0/ ∗ ) = {ε}.
7
8
Verallgemeinerte endliche Automaten
Definition:
Ein verallgemeinerter endlicher Automat ist ein 5-Tupel
(K, Σ, ∆, s, F), wobei gilt:
• K ist eine endliche Menge von Zuständen,
Eliminieren von Zuständen
Um einen Zustand q zu eliminieren betrachte alle qi , qj ∈ K mit
q 6= qi und q 6= qj sodass (qi , α, q) ∈ ∆ und (q, β , qj ) ∈ ∆.
Wenn einer der Übergänge (qi , δ , qj ) oder (q, γ, q) nicht existiert,
setze δ = 0/ beziehungsweise γ = 0.
/
γ
• Σ ist ein Alphabet,
• ∆ ⊆ K × R(Σ) × K ist die Überführungsrelation oder auch
Übergangsrelation, wobei R(Σ) die Menge der regulären
Ausdrücke über dem Alphabet Σ sei,
• s ∈ K ist der Startzustand und
• F ⊆ K ist die Menge der Endzustände.
qi
α
q
β
qj
qi
δ ∪ αγ ∗ β
qj
δ
Ersetze nun die Übergänge (qi , α, q), (q, β , qj ), (qi , δ , qj ) und
(q, γ, q) durch den neuen Übergang (qi , δ ∪ αγ ∗ β , qj ).
9
10
NEA → regulärer Ausdruck
Beispiel
Sei M = (K, Σ, ∆, s, F) ein NEA. O.B.d.A. dürfen wir annehmen,
dass M genau einen Endzustand f besitzt. Wir dürfen ferner
o.B.d.A. annehmen, dass im zugehörigen Zustandsgraphen in s
keine Kanten enden und von f keine Kanten ausgehen.
a
q2
ε
s
ε
M
f
q0
Wir eliminieren nun alle Zustände außer s und f . Dies liefert einen
verallgemeinerten Zustandsgraphen mit zwei Zuständen, für den
ein zugehöriger regulärer Ausdruck direkt abgelesen werden kann.
η
s
b
b
q1
b
a
a
L(M) = {w ∈ {a, b}∗ : |w|b ≡ 1 mod 3}
f
11
12
Beispiel
Beispiel
a
a
q2
q2
s
ε
q0
b
a
b
b
b
b
q1
ε
s
f
ε
q0
b
a
a
q1
ε
f
a
Um q2 zu eliminieren ersetzen wir den Pfad q1 → q2 → q0 durch
den entsprechenden Übergang (q1 , ba∗ b, q0 ).
Wir fügen einen neuen Startzustand s ohne eingehende Kanten und
einen neuen Endzustand f ohne ausgehende Kanten hinzu.
13
14
Beispiel
Beispiel
ba∗ b
s
ε
q0
b
a
ba∗ b
q1
ε
s
f
ε
a
q0
b
a
Um q2 zu eliminieren ersetzen wir den Pfad q1 → q2 → q0 durch
den entsprechenden Übergang (q1 , ba∗ b, q0 ).
q1
ε
f
a
Um q1 zu eliminieren ersetzen wir zunächst den Pfad q0 → q1 → q0
durch den entsprechenden Übergang (q0 , a ∪ ba∗ ba∗ b, q0 ).
15
16
Beispiel
Beispiel
a ∪ ba∗ ba∗ b
s
ε
q0
a ∪ ba∗ ba∗ b
b
q1
ε
f
a
Um q1 zu eliminieren ersetzen wir zunächst den Pfad q0 → q1 → q0
durch den entsprechenden Übergang (q0 , a ∪ ba∗ ba∗ b, q0 ).
s
ε
q0
b
q1
ε
f
a
Um q1 zu eliminieren ersetzen wir danach den Pfad q0 → q1 → f
durch den entsprechenden Übergang (q0 , ba∗ , f ).
17
18
Beispiel
Beispiel
a ∪ ba∗ ba∗ b
s
ε
q0
a ∪ ba∗ ba∗ b
ba∗
ε
s
f
Um q1 zu eliminieren ersetzen wir danach den Pfad q0 → q1 → f
durch den entsprechenden Übergang (q0 , ba∗ , f ).
q0
ba∗
f
Um q0 zu eliminieren ersetzen wir den Pfad s → q0 → f durch den
entsprechenden Übergang (s, (a ∪ ba∗ ba∗ b)∗ ba∗ , f ).
19
20
Beispiel
Beispiel
a
q2
b
b
s
∗
(a ∪ ba∗ ba∗ b) ba∗
q0
f
a
Um q0 zu eliminieren ersetzen wir den Pfad s → q0 → f durch den
entsprechenden Übergang (s, (a ∪ ba∗ ba∗ b)∗ ba∗ , f ).
b
q1
s
(a ∪ ba∗ ba∗ b)∗ ba∗
f
a
L(M) = {w ∈ {a, b}∗ : |w|b ≡ 1 mod 3} = L((a ∪ ba∗ ba∗ b)∗ ba∗ )
21
22
23
24
25
26
Reguläre und nichtreguläre Sprachen
dec : N0 → {0, 1, . . . , 9}∗
Pumping Lemma für reguläre Sprachen
Dezimaldarstellung
Satz (Pumping Lemma):
Sei L eine reguläre Sprache. Dann gibt es eine Zahl n, so dass sich
alle Wörter w ∈ L mit |w| ≥ n in w = xyz zerlegen lassen, so dass
{w ∈ {0, 1, . . . , 9}∗ | dec−1 (w) ist durch 3 teilbar }
{an | n ist eine durch 3 teilbare Zahl }
{ap | p ist eine Primzahl }
(1)
{w ∈ {a, b}∗ | w enthält gleichviele a und b}
(3)
(2)
y 6= ε
|xy| ≤ n
xyk z ∈ L für alle k ≥ 0
{w ∈ {a, b, c}∗ | w enthält gleichviele a und b}
27
Beweis: Sei M = (K, Σ, δ , s, F) ein DEA, der L akzeptiert, und sei
n = |K|. Sei w = w1 w2 . . . wn u ∈ L, wobei wi ∈ Σ für i = 1, . . . , n und
u ∈ Σ∗ .
Dann gibt es n + 1 Konfigurationen, so dass
28
Wegen i < j gilt y 6= ε.
Sei x = w1 . . . wi . Nach Konstruktion ist |xy| ≤ n.
Sei z = wj+1 . . . wn u.
(q0 , w1 w2 . . . wn ) `M (q1 , w2 . . . wn ) `M · · · `M (qn , ε)
Wegen (q0 , x) `∗M (qi , ε) und (qi , y) `∗M (qi , ε) und
(qi , z) `∗M (qn , u) gilt für alle k ≥ 0
mit q0 = s.
Nach dem Schubfachprinzip muss es i, j mit 0 ≤ i < j ≤ n geben, so
dass qi = qj . Wir wählen y = wi+1 . . . wj . Dann gilt
(q0 , xyk z) `∗M (qi , yk z) `∗M (qi , z) `∗M (qn , u) `∗M (f , ε)
für ein f ∈ F, also xyk z ∈ L.
(qi , y) `∗M (qi , ε)
29
Pumping Lemma:
30
Pumping Lemma:
für alle
gilt, es gibt
so dass für alle
gilt, es gibt
so dass für alle
gilt
L ∈ REG
∀
∃
∀
∃
∀
n≥1
w ∈ L, |w| ≥ n
x, y, z, |xy| ≤ n, y 6= ε, w = xyz
i≥0
xyi z ∈ L
L ∈ REG
n≥1
w ∈ L, |w| ≥ n
x, y, z, |xy| ≤ n, y 6= ε, w = xyz
i≥0
xyi z ∈ L
31
Beispiele:
L1 = {ak bk | k ≥ 0} ist nicht regulär:
Angenommen, L1 wäre regulär. Dann gäbe es ein n, so dass sich
alle Wörter der Länge mindestens n wie im Pumping Lemma
angegeben zerlegen ließen.
an bn .
Betrachte w =
Dieses Wort müsste sich also in xyz zerlegen
lassen, so dass xyi z ∈ L1 für alle i ≥ 0. Da |xy| ≤ n, bestünde y nur
aus a und xyi z enthielte unterschiedlich viele a und b für alle i 6= 1.
Widerspruch!
L2 = {w ∈
{a, b}∗
32
L3 = {ap | p ist eine Primzahl} ist nicht regulär.
Angenommen, L3 wäre regulär. Dann gäbe es ein n, so dass sich
alle Wörter w = ap mit p ≥ n wie im Pumping Lemma angegeben
zerlegen ließen. Sei also w = xyz mit
x = ar , y = as , z = at ,
xyi z
Für alle i ≥ 0 müsste dann
=
zu L3 gehören, d.h.,
r + i · s + t müsste für alle i ≥ 0 eine Primzahl sein. Insbesondere
auch für i = r + 2s + t + 2, aber
r + is + t = r + rs + 2s2 + ts + 2s + t
| w enthält gleichviele a und b} ist nicht regulär:
L1 = L(a∗ b∗ ) ∩ L2
r, t ≥ 0, s > 0
ar+i·s+t
= (s + 1)(r + 2s + t)
Widerspruch!
33
34
Homomorphismen
L4 = {ww | w ∈ {a, b}∗ } ist nicht regulär.
Seien Σ und Γ Alphabete.
Angenommen, L4 wäre regulär. Dann gäbe es ein n, so dass sich
alle Wörter der Länge mindestens n wie im Pumping Lemma
angegeben zerlegen ließen.
Eine Funktion h : Σ∗ → Γ∗ mit
h(uv) = h(u)h(v)
Betrachte an bn an bn . Dieses Wort müsste sich also in xyz zerlegen
lassen, so dass xyi z ∈ L4 für alle i ≥ 0. Da |xy| ≤ n, wäre xy ∈ L(a∗ ).
für alle u, v ∈ Σ∗ heißt Homomorphismus.
Für i = 2 würde die zweite Worthälfte nun aber mit b beginnen, die
erste aber weiterhin mit a. Widerspruch!
Es gilt stets h(ε) = ε. Ferner ist ein Homomorphismus bereits
durch seine Werte auf Σ eindeutig bestimmt.
35
36
Beispiel:
Σ = Γ = {a, b}, h(a) = ab, h(b) = aab
Beispiel:
h(aab) = h(a)h(ab) = h(a)h(a)h(b) = ababaab
Σ = {a, b, c}, Γ = {a, b}, h(a) = a, h(b) = b, h(c) = ε
Satz:
Sei h : Σ∗ → Γ∗ ein Homomorphismus. Falls L ⊆ Σ∗ eine reguläre
Sprache ist, dann ist auch h(L) = {h(w) | w ∈ L} eine reguläre
Sprache.
L = {an bk ck | n ≥ 0, k ≥ 0}
h(L) = L( a∗ b∗ )
h−1 (h(L)) = L( (c∗ a∗ )∗ c∗ (b∗ c∗ )∗ )
Satz:
Sei h : Σ∗ → Γ∗ ein Homomorphismus. Falls B ⊆ Γ∗ eine reguläre
Sprache ist, dann ist auch h−1 (B) = {w | h(w) ∈ B} eine reguläre
Sprache.
37
Beispiel:
L5 =
{ci aj ck bl cm
38
Beispiel:
| i, j, k, l, m ≥ 0, j = l} ist nicht regulär:
L6 = {aj bk cl | j, k, l ≥ 0 und k = l falls j = 1}
Angenommen, L5 wäre regulär. Betrachte Homomorphismus
h : {a, b, c}∗ → {a, b}∗ mit h(a) = a, h(b) = b, h(c) = ε. Dann
müsste auch h(L5 ) regulär sein. Aber
L6 erfüllt das Pumping Lemma: Alle w ∈ L6 mit |w| ≥ 3 lassen sich
entsprechend der Bedingungen des Pumping Lemmas so in xyz
zerlegen, dass alle aufgepumpten Wörter xyi z, i ≥ 0, auch zu L6
gehören.
h(L5 ) = {an bn | n ≥ 0}
Wir unterscheiden vier Fälle:
ist nicht regulär. Widerspruch!
39
w enthält mindestens drei a. Wähle x = ε und y = a. Man beachte,
dass durch Aufpumpen kein Wort entstehen kann, das genau ein a
enthält.
L(aab∗ c∗ ).
w enthält genau zwei a, d.h., w gehört zu
Wähle
x = ε und y = aa. Man beachte, dass durch Aufpumpen kein Wort
entstehen kann, das genau ein a enthält.
w enthält genau ein a. Dann ist w von der Form
x = ε und y = a.
abk ck .
Wähle
w enthält kein a. Dann gehört w zur Sprache L(b∗ c∗ ), die in L6
enthalten ist und regulär ist. . . .
40
L6 ist jedoch nicht regulär!
Angenommen, L6 wäre regulär. Dann wäre auch L6R regulär! Dann
gäbe es also ein n, so dass sich alle Wörter aus L6R der Länge
mindestens n wie im Pumping Lemma angegeben zerlegen ließen.
Es ist L6R = {cl bk aj | j, k, l ≥ 0 und k = l falls j = 1}
Betrachte w = cn bn a. Da |xy| ≤ n, bestünde y nur aus c und xyi z
enthielte unterschiedlich viele c und b und weiterhin genau ein a
für alle i 6= 1. Widerspruch!
41
42
Reguläre Grammatiken
Definition:
L ∈ REG ⇒ Pumping Lemma erfüllt
(a) Eine Grammatik G = (V, Σ, R, S) heißt rechtslinear, falls alle
Regeln in R von der Form A → aB oder A → ε sind mit
A, B ∈ V und a ∈ Σ.
¬(L ∈ REG) ⇐ ¬(Pumping Lemma erfüllt)
(b) Eine Grammatik G = (V, Σ, R, S) heißt linkslinear, falls alle
Regeln in R von der Form A → Ba oder A → ε sind mit
A, B ∈ V und a ∈ Σ.
Pumping Lemma erfüllt 6⇒ L ∈ REG
(c) Eine Grammatik heißt regulär, wenn sie rechtslinear oder
linkslinear ist.
43
Satz:
Die von den regulären Grammatiken erzeugten Sprachen sind
genau die regulären Sprachen.
44
Beispiel:
Beispiel:
S
b
a
s
p
a
b
a, b
q
S
S
P
P
P
Q
Q
→
→
→
→
→
→
→
→ aA
b
A → bA
bS
aP
aQ
bQ
ε
aP
bS
A → aB
B → aA
B → ε
45
S
a
A
a
a
B

Download Report