Eine Charakterisierung regulärer Sprachen

Eine Charakterisierung regulärer Sprachen
Vorlesung Theoretische Grundlagen der Informatik
Nun kommen wir zum Beweis des Satzes.
Satz 1 Sei Σ ein Alphabet und L ⊆ Σ∗ eine
Sprache. L ist genau dann regulär, wenn min- Wir zeigen zunächst den einfachen Teil: wenn
destens eine der folgenden sechs Aussagen gilt. eine der sechs Aussagen gilt, so ist L regulär.
Dazu reicht es, für jeden der sechs Fälle einen
(i) L = ∅.
NEA zu konstruieren, der L erkennt. Abbildung 1 zeigt NEA für die Fälle (i)–(iii).
(ii) L = {ε}.
(iii) L = {s} für ein s ∈ Σ.
(iv) L = L1 ∪ L2 für reguläre Sprachen
L1 , L2 ⊆ Σ∗ , L1 , L2 6= L.
(v) L = L1 ◦L2 für reguläre Sprachen L1 , L2 ⊆
Σ∗ , L1 , L2 6= L.
s
(vi) L = L∗1 für eine reguläre Sprache L1 ⊆
Abbildung 1: Erkennende NEA für L = ∅
Σ∗ , L1 6= L.
(oben), L = {ε} (Mitte), L = {s} (unten)
Bevor wir den Satz beweisen, eine kleine Bemerkung: Die Bedingungen L1 , L2 6= L in (iv)
Für die anderen drei Fälle setzen wir den
und (v) sowie L1 6= L in (vi) sind wichtig; for- NEA aus erkennenden DEA M1 für L1 und–im
dern wir sie nicht, wäre z.B. Aussage (iv) für Fall von (iv),(v)–M2 für L2 zusammen; diese
jede reguläre Sprache in trivialer Weise erfüllt, existieren, weil L1 und L2 nach Voraussetzung
weil ja
regulär sind. Abbildung 2 zeigt M1 und M2
sowie ihre Start- und akzeptierenden Zustände
L = L1 ∪ L2 , mit L1 = L, L2 = ∅.
schematisch.
Auch Aussage (v) würde dann immer gelten
wegen
L = L 1 ◦ L2 ,
mit L1 = L,
L2 = {e}.
Aussage (vi) schliesslich würde automatisch
gelten, falls L der Stern von sich selbst ist–
was durchaus passieren kann.1 In der Variante des Satzes aus der Vorlesung kamen diese
Bedingungen nicht vor, weshalb wir auch immer Eigenschaft (iv) folgern konnten, so dass
die Frage offen blieb, wozu die anderen Eigenschaften eigentlich notwendig sind.
Abbildung 2: Erkennende DEA M1 für L1
1
n
∗
(oben),
M2 für L2 (unten)
Für L = {0 | n ∈ IN } gilt L = L .
1
zeptierenden Zustand, der nach Erreichen nie
wieder verlassen werden kann (auch das muss
in M nicht der Fall sein). Abbildung 4 skizziert
die Hilfskonstruktion.
Abbildung 3 zeigt erkennende NEA für die
Fälle (iv)–(vi). Eine kleine Feinheit ist noch,
dass man in der Konstruktion für L∗1 eine neuen (akzeptierenden) Startzustand benötigt, damit das leere Wort ε, das ja immer in L∗1 ist,
auf jeden Fall akzeptiert wird.
q-1
ε
ε
qn+1
ε
ε
Abbildung 4: Hilfs-NEA M 0 am Beispiel des
DEA M = M2 aus Abbildung 2 (unten)
ε
Nun definieren wir eine ganze Klasse von Sprachen bzgl. des Automaten
M 0 = ({q−1 , . . . , qn+1 }, Σ, δ, q−1 , F ). Für
Indices i, j, k mit
i ∈ {0, . . . , n + 1},
j, k ∈ {−1} ∪ {` | i ≤ ` ≤ n + 1}
ε
ε
definieren wir
ε
∆i (j, k)
als die Menge der Wörter w ∈ Σ∗ mit der folgenden Eigenschaft: in M 0 gibt es einen zulässigen Weg, der
ε
ε
(a) im Zustand qj beginnt und im Zustand qk
endet,
ε
(b) nur über Zwischenzustände q` , 0 ≤ ` < i
führt,
ε
Abbildung 3: Erkennende DEA für L1 ∪ L2
(oben), L1 ◦ L2 (Mitte), L∗1 (unten)
(c) w verarbeitet.
Formal heisst das: w kann für ein t ≥ 0 in
Nun beweisen wir die Umkehrung: wenn L der Form w1 . . . wt geschrieben werden, wobei
regulär ist, so gilt eine der Aussagen (i)–(vi). wu ∈ Σ ∪ {ε} für 1 ≤ u ≤ t, und es gibt Indices
Sei also L regulär und M ein DEA, der L m0 , m1 , . . . , mt mit
erkennt. M habe n + 1 Zustände q0 , . . . , qn , für
(a) m0 = j, mt = k,
irgendein n ≥ 0. In einem Hilfsschritt transformieren wir M zunächst in einen äquivalenten (b) 0 ≤ m < i für 1 ≤ u < t, und
u
(also ebenfalls L erkennenden) NEA M 0 . M 0
hat einen Startzustand q−1 , der nicht akzep- (c) qmu ∈ δ(qmu−1 , wu ), für 1 ≤ u ≤ t.
tierend ist und nach Verlassen nie wieder erreicht werden kann (dies muss in M nicht der Hier sind zwei Beispiele zur Illustration dieser
Fall sein). Ausserdem hat M 0 genau einen ak- Definition.
2
Beobachtung 2 Für alle j, k ∈ {−1, . . . , n + Das bedeutet, ∆n+1 (−1, n + 1) enthält genau
die Wörter aus L, denn M 0 erkennt ja genauso
1} gilt: jedes w ∈ ∆0 (j, k) ist von der Form
wie M die Sprache L.
w = ε oder w = s, s ∈ Σ.
Hier ist das entscheidende
Ferner gilt ∆n+1 (−1, n + 1) = L.
Lemma 3 Sei i ∈ {1, . . . , n+1}, j, k ∈ {−1}∪
Um den ersten Teil zu sehen, beobachten wir {` | i ≤ ` ≤ n + 1}. Definiere
zunächst, dass ∆0 (j, k) nur Wörter enthält, die
durch einen direkten Pfeil von qj nach qk verarL1 := ∆i−1 (j, k),
beitet werden – Zwischenzustände sind laut (b)
L2 := ∆i−1 (j, i − 1),
(1)
nicht zugelassen. Dies sind genau die Wörter,
L3 := ∆i−1 (i − 1, i − 1),
die aus einem Symbol auf dem Übergangspfeil
L4 := ∆i−1 (i − 1, k).
von qj nach qk bestehen. Als Symbole können
genau ε und alle s aus Σ vorkommen. ∆0 (j, j) Dann gilt
enthält nach Definition immer das leere Wort
∆i (j, k) = L1 ∪ (L2 ◦ L∗3 ◦ L4 ).
ε.
Da insbesondere ’Startzustand’ qj und ’Zielzustand’ qk nicht als Zwischenzustände auftre- Beweis. Betrachte ein Wort w ∈ ∆i (j, k) und
ten dürfen, können Pfeile von qj nach qj und den zulässigen Weg mit den Eigenschaften (a),
von qk nach qk (’Schleifen’) nur durchlaufen (b) und (c), der beweist, dass w ∈ ∆i (j, k) gilt.
Es gibt zwei Fälle.
werden, wenn qj = qk gilt, und dann auch nur
(1) Der Weg verwendet den Zustand
einmal ! Insofern kann auch in diesem Fall ein
Wort in ∆0 (j, k) nur aus einem Symbol beste- qi−1 nicht; dann ist w nach Defintion in
hen, im Gegensatz zu dem, was in der Vorle- ∆i−1 (j, k) = L1 .
sung gesagt wurde.
(2) Der Weg verwendet den Zustand qi−1 .
Für j 6= k gibt es natürlich auch die Möglich- Dann schreiben wir w in der Form w = xyz,
keit, dass ∆0 (j, k) leer ist, nämlich dann, wenn wobei x das Teilwort ist, nach dessen Verarbeies keine Übergangspfeile von qj nach qk gibt. tung zum ersten Mal der Zustand qi−1 erreicht
Abbildung 5 illustriert die möglichen Fälle.
wird, und xy das Teilwort, nach dessen Verarbeitung
der Zustand qi−1 zum letzten Mal
s1,s3
erreicht wird. Es gilt
qj
s2,ε
qk
x ∈ ∆i−1 (j, i − 1) = L2 ,
y ∈ ∆i−1 (i − 1, i − 1)∗ = L∗3 ,
z ∈ ∆i−1 (i − 1, k) = L4 .
Abbildung 5: Für den abgebildeten Auschnitt
eines NEA gilt: ∆0 (j, k) = {ε, s2 }, ∆0 (j, j) =
{ε, s1 , s3 }, ∆0 (k, k) = {ε}, ∆0 (k, j) = ∅.
Dazu beobachten wir, dass die Verarbeitung
von x entlang des Weges von w den Automaten von qj nach qi−1 führt, nach Definition von
x ohne Verwendung von qi−1 als Zwischenzustand. Die anschliessende Verarbeitung von y
bringt den Automaten möglicherweise mehrmals von qi−1 nach qi−1 , wobei qi−1 dazwischen jeweils nicht verwendet wird. z schliesslich bringt den Automaten von qi−1 nach qk ,
nach Definition von xy wiederum ohne Verwendung von qi−1 als Zwischenzustand. (Jedes der
drei Teilwörter x, y, z kann übrigens leer sein.)
Für den zweiten Teil der Beobachtung vergegenwärtigen wir uns nocheinmal die Definition: ∆n+1 (−1, n+1) besteht aus allen Wörtern,
die entlang eines zuläsigen Weges vom Startzustand zum akzeptierenden Zustand von M 0
verarbeitet werden. Dass dabei nur Zwischenzustände q0 , . . . , qn erlaubt sind, ist keine Einschränkung, da wir durch die Hilfskonstruktion
sicher gestellt haben, dass q−1 und qn+1 ohnehin nie als Zwischenzustände auftreten können.
3
Entweder ist L also von einer der Formen (i)–
(iii), oder L enthält mindestens ein nichtleeres
Wort s, für ein Symbol s ∈ Σ. Dann gilt L =
{s} ∪ (L \ {s}). Als endliche Sprachen sind
Aus (1) und (2) folgt
w ∈ L1 ∪ (L2 ◦ L∗3 ◦ L4 ),
und da dies für alle w ∈ ∆i (j, k) gilt, folgt auch
L1 := {s},
∆i (j, k) ⊆ L1 ∪ (L2 ◦ L∗3 ◦ L4 ).
L2 := L \ {s}
regulär, es gilt L1 , L2 6= L, also Aussage (iv).
Nehmen wir nun an, das Lemma gelte bereits
für i − 1. Lemma 3 besagt, dass
Umgekehrt gilt aber auch
L1 ∪ (L2 ◦ L∗3 ◦ L4 ) ⊆ ∆i (j, k) :
L = ∆i (j, k) = L1 ∪ (L2 ◦ L∗3 ◦ L4 )
jedes Wort in L1 ist nach Definition auch in
∆i (j, k); auch jedes Wort w 0 ∈ L2 ◦ L∗3 ◦
L4 bringt den Automaten von qj nach qk ,
unter auschliesslicher Verwendung der Zwischenzustände q0 , . . . , qi−1 . Denn w0 ist ja aus
Teilwörtern zusammengesetzt, wobei das erste Teilwort in L2 , das letzte in L4 und die
dazwischenliegenden in L3 sind. Wir können
dann einfach die Wege, die laut Definition von
L2 , L∗3 , L4 existieren, zusammensetzen.
Nun können wir endlich den Beweis von Satz
1 abschliessen, und zwar mit folgendem Lemma, aus dem mit L = ∆n+1 (−1, n+1) der Satz
folgt.
gilt, wobei L1 , . . . L4 wie in (1) definiert sind–
insbesondere sind diese vier Sprachen von der
Form ∆i−1 (·, ·) und damit nach Induktionsannahme regulär. Das Ziel ist es nun, L1 (und
gegebenenfalls L2 ) mit den im Lemma geforderten Eigenschaften zu finden. Dazu betrachten wir mehrere Fälle.
(1) L ist selbst eine der Sprachen L1 , . . . L4 .
Nach Induktionsannahme gilt für L damit eine der Aussagen (i)–(vi). Im folgenden sei also
L 6= L1 , . . . L4 .
(2) L 6= L2 ◦ L∗3 ◦ L4 . Dann setze
L1 := L1 ,
L2 := L2 ◦ L∗3 ◦ L4 .
Lemma 4 Seien i, j, k wie oben, L = ∆i (j, k). Nach der ‘einfachen’ Richtung von Satz 1 sind
Dann gilt mindestens eine der folgenden Aus- L und L regulär, weil sie mittels regulärer
1
2
sagen:
Operatoren aus regulären Sprachen ∆i−1 (·, ·)
zusammengesetzt sind. Wegen L 6= L1 , L2 folgt
(i) L = ∅.
Aussage (iv). Im folgenden sei also L = L2 ◦
(ii) L = {ε}.
L∗3 ◦ L4 .
(3) L 6= L∗3 ◦ L4 . Dann setze
(iii) L = {s} für ein s ∈ Σ.
L1 := L2 , L2 := L∗3 ◦ L4 .
(iv) L = L1 ∪ L2 für reguläre Sprachen
L1 , L2 ⊆ Σ∗ , L1 , L2 6= L.
Wie vorher sind dann L1 und L2 regulär, es
gilt L 6= L1 , L2 und damit (v). Im folgenden
(v) L = L1 ◦L2 für reguläre Sprachen L1 , L2 ⊆
sei also L = L∗3 ◦ L4 .
Σ∗ , L1 , L2 6= L.
(4) L 6= L∗3 . Dann setze
∗
(vi) L = L1 für eine reguläre Sprache L1 ⊆
L1 := L∗3 , L2 := L4 .
Σ∗ , L1 6= L.
Wiederum folgt (v).
Insbesondere ist L regulär.
(5) L = L∗3 . Wir setzten
Beweis. Induktion über i. Für i = 0 ergibt
L1 := L3
sich aus Beobachtung 2, dass L = ∆0 (j, k) eine
endliche Sprache ist, wobei jedes Wort das leere und erhalten (vi).
Wort ist oder nur aus einem Symbol besteht.
4

Download Report