Sprachen die nicht regulär sind ; Pumping -Lemma für regulär Sprachen.
Pumping-Lemma
Idee des Pumping -Lemmas
Definition
Beweis und Beispiel
Abschlusseigenschaften regulärer Sprachen.
Testen von Eigenschaften regulär Sprachen ( Leerheit, Unendlichkeit, Gleichheit usw.)
Sprachen die nicht regulär sind ; Pumping -Lemma für regulär Sprachen.
Pumping-Lemma
2.1 Idee des Pumping-Lemmas
Definition
Beweis und Beispiel
1. Definition: Eine Sprache L Ì S*, für die ein regulär Ausdruck a existiert mit L=L(a), heißt reguläre Sprache.
Sei S ein Alphabet , die regulären Ausdrucken über S sind.
1) Æ ist ein regulärer Ausdruck und bezeichnet die leere Menge.
2) Î ist ein regulärer Ausdruck und bezeichnet die Menge {Î}.
3) Für jedes a aus S ist a ein regulärer Ausdruck und bezeichnet die Menge {a}.
4) Wenn r und s reguläre Ausdrücken sind, die die Sprachen R und S bezeichnen, so
sind (r + s),(rs) und (r*) ebenfalls reguläre Ausdrücke und bezeichnen die Menge
R ÈS, RS bzw. R*.
Beispiele für reguläre Sprache.
1) L={w Î {0,1}* | w enthält 10 nicht als Teilwort}.
L = L(0*1*).
2) L = {w Î{0,1}*| w enthält 101 als Teilwort}.
L = L(( 0 +1)*101(0 +1)*).
2.Pumping-Lemma
Idee
Das Pumping-Lemma für reguläre Menge besagt, dass jede genügend lange Zeichenkette aus einer regulären Menge eine kurze Teil-Zeichenkette enthält
Die gepumpt werden kann. Wenn wir also beliebig viele Kopien der Teil-Zeichenkette
einfügen, erhalten wir immer wieder eine Zeichenkette aus der regulären Menge.
Definition
Sei L eine reguläre Sprache , M = (Q, S, d, S ,F) zugehörigen deterministischen endlichen Automat, betrachten wir Eingabe W Î L mit |W| >= L wobei
L = Anzahl der Zustände.
Betrachte Rechnung für W= a1.......an
a1 a2 an
--à qo àq1--à ---------- --àqn
es gibt nur L < n+1 Zustände also muss mindestens einer q mehrfach in der Rechnung vorkommen.
qo-à q--à q--à qn
W = u v x
Zerlegung w = uvx mit d(s, u) = q
d( q, v) = q
d(q, x) = qn ÎF
damit gilt auch d(s, u ,v^i x ) = d(d(d(d(s, u), v), v), x) (i-mal wiederholt)
also u v^i x ÎL für i = 0,1,2,3,------.
Lemma: L sei eine reguläre Menge. Es gibt eine Konstante n, so dass sich jedes Wort z aus L mit |z| ? n als z = uvx mit | uv| ? n und | v|? 1 schreiben lässt und für alle i ? 0. gilt, dass u v^i x in L ist. Außerdem ist n größer als die Anzahl der Zustände in dem kleinsten EA, der L akzeptiert.
Beweis:
Sei w = a1a2......an mit u = a1a2...aJ, v = aj+k .... ak und x = ak+1 .... an.
Beachten sie , dass das pumping Lemma besagt , dass eine reguläre Menge, wenn sie eine lange Zeichenkette W enthält, unendlich viele Zeichenketten der Form uv^ix enthält. Das Lemma besagt nicht , dass jede genügend lange Zeichenkette in einer regulären Menge von der Form uv^i x für ein größes i ist.
Mit dem Pumping- Lemma kann man zeigen, dass gewisse Sprachen nicht regulär sind.
Beispiel:
Sei L = {a^n b^n | n Î?} = { ?,ab, aabb, -----}
Behauptung: L ist nicht regulär.
Beweis: Angenommen, L ist regulär.
betrachten wir das Wort w ÎL
mit | w| ³ l; l die Konstante aus dem Pumping Lemma.
W= aaa --- abb---b
Zerlegung w = uvx
Mögliche Fälle
a) vÎ{a}*dann hat das Wort uv^2 x mehr a's als b's also nicht mehr Î L Widerspruch.
b) vÎL(aa* bb*) v enthält a's und b's dann ist uv^2x ÏL(a*b*) also nicht in L, Widerspruch.
c) vÎ L(b*) dann hat uv^2 x mehr b's als a's also uv^2x Ï L wieder Widerspruch.
Also Annahme falsch , da haben wir gezeigt, dass L nicht regulär ist.
Abschlusseigenschaften regulärer Sprachen
Sprachklasse ist unter einer Operation abgeschlossen Grundweise auf beliebige Sprachen der Klasse Operation angewandt dann ist Ergebnis wieder in der Klasse.
Satz: Regulären Sprachen sind abgeschlossen unter
a) Vereinigung , b) Durchschnitt, c) Komplement, d) *-Operation, e) Konkatenation .
seien L1 und L2 zwei Sprachen dann gilt
a) L1ÈL2 , b) L1ÇL2, c) å*\ L1 d) L1* und e) L1*L2.
Beweise:
Für c) å*\L.
L sei L(M) für einen DEA M= (Q, å1, d, qo, F ) und es gelte L Í å* . Als erstes nehmen wir å1= å an, denn falls es Symbole in å1 gibt, die nicht in å sind, dann löschen wir alle Symbole aus M, die nicht in å in sind. Sei dÎM dann gilt d(q, a)=d für alle aÎå und d(q ,a )=d qÎQ, aÎå- å1. um nur å* - L zu akzeptieren, bilden wir der Endzuständen von M sei M' = (Q, å, d qo, Q -F) Dann M' genau ein Wort w so dass d(q0,w) in Q-F liegt dh w in å*- L . ( M soll deterministisch soll und keine ?- Bewegungen machen.
Für b) L1ÇL2.
Es gilt L1ÇL2 = Ø(L1ÈL2)
Bemerkenswert ist, dass auch eine direkte Konstruktion eines DEA für die Schnittbildung zweier reguläre Mengen existiert. Die Konstruktion umfasst die Bildung des Kartesischen Produkts von Zuständen,
sei M1 = ( Q1, å1, d1, q1, F1) , M2 = ( Q2, å2, d2, q2, F2) zwei DEA , durch direkt Produkt zeigen wir, dass
L(A1 Ä A2)= L(A1) ÇL(A2)
A1ÄA2 = (Q, å, d, qo , F )
Q = Q1 Ä Q2
= { (q1, q2)| qi ÎQ}.
qo = (qo1, qo2)
d(( q1, q2 ), a) = ( d1(q1,a) , d2(q2, a))
F = F1 Ä F2.
= { (q1,q2)| qi Î Fi} .
um zu zeigen , dass
d(qo,w) = (d1(qo1,w) , d1(qo2,w))
somit wÎL(A1 Ä A2) Û d( qo, w) Î F
Û (d1(qo1,w), d1(qo2,w)) ÎF
Û d1(qo1,w) Î F1 & d1(qo2,w) ÎF2
Û w Î L(A1) & w Î L(A2)
Û w ÎL(A1) Ç L(A2).
Für a) , d) und e) folgt aus Darstellung der regulären Ausdrücken ,
kann man auch durch Kombinationen von Automaten die Disjunkte Summe, die Verkettung(Konkatenation) und die Iteration(*-Operation) zeigen.
Beweis:
Seien gegeben die Automaten Ai = (Q , å , qoi ,Fi , di) für i = (1, 2) mit Q1 È Q2 = Æ und B.
a) Die disjunkte Summe der beide Automaten A = A1 ? A2 = (Q, å, qo, F, d) ist festgelegt durch:
Q = Q1? Q2 ? {qo}
qo ein neuer Zustand,
F = F1 ? F2 ,
d(q, a) = d1(q ,a) falls q ÎQ1
d2(q, a) falls q ÎQ2
{qo1,qo2} falls q = qo und a = Î
e) Die Verkettung A = A1A2 = ( Q, å, qo1 F2, d) der beiden Automaten A1 und A2 ist definiert durch :
Q = Q1 ?Q2,
d (q, a) = d1(q, a) falls q Î Q1 \ F1
oder qÎ Q1 mit a ¹ e
d1(q, e) È {qo2} falls q ÎF1 mit a= e
d2(q, a) falls q Î Q2.
d)die Iteration A = B* =( Q È {qa, qf}, å, qa, {qf}, d) wird festgelegt durch:
d(q, a) = {qo, qf} falls q = qa, a = e
dB(q , e) È {qo, qf} falls q ÎF, a = e
dB(q, a) sonst.
Testen von Eigenschaften regulärer Sprachen ( Leerheit, Unendlichkeit, Gleichheit usw.)
Beweis:
sei w ein kürzeres als aller anderen akzeptierten Wörter. Nach dem Pumping-Lemma gilt | w|< n , denn wenn w das kürzeste Wort wäre und | w| ³ n gelten würde, so wäre w = uvy und uy wäre ein kürzeres Wort aus der Sprache.
Wenn w aus L(M) und n £ |w|< 2n gilt , dann ist L(M) nach dem pumping- Lemma
Unendlich: w = w1w2w3 und für alle i ist w1w2^i w3 in L. Umgekehrt gilt , wenn L(M) unendlich ist dann gibt es ein w in L(M) mit |w| ³ n. Wenn |w|< 2n gilt , dann sind wir fertig. Falls kein Wort eine Länge zwischen n und 2n - 1 hat, dann sei w das kürzeste Wort der Länge mindestens 2n. Wiederum gilt nach dem Pumping -Lemma w = w1w2w3 mit 1 £ | w2| £ n und w1w3 in L(M). Entweder war w nicht
Ein kürzestes Wort der Länge größer oder gleich 2n, oder | w1w3| liegt zwischen
n und 2n - 1 , in jedem Fall erhalten wir ein Widerspruch.
Satz2: Es gibt Algorithmus, um zu entscheiden, ob zwei endlichen Automaten äquivalent sind (dh ob sie die gleiche Sprachen akzeptieren).
Beweis:
Seien M1 und M2 EA, die L1 bzw L2 akzeptieren, folgt dass (L1ÇL2/)È(L1/ÇL2) von einem endlichen Automaten M3 akzeptiert wird. Es ist einfach zu sehen ,dass
M3 genau dann ein Wort akzeptiert, wenn L1 ¹ L2. Also gilt es nach Satz1 einem
Algorithmus, um zu entscheiden, ob L1 = L2.