Pumping lemma for regular sets Zusammenfassung

Pumping lemma for regular sets
Zusammenfassung
Wu Ji
1. Grund
Bis jetzt haben wir schon FA studiert. Und wir wissen, was es machen kann.
Jetzt suchen wir, was es nicht schaffen kann.
Beispiel:
B = {anbn | n ≥ 0}
Um Sprache B zu akzeptieren, muss der Automat die Anzahl von a und die
Anzahl von b speichern. Aber es ist unmöglich. Da anbn hat unendlichen
vielen verschiedene Form, z.B. {ab, aabb,aaabbb,...}. FA hat nur endliche
Zustände. Es kann nicht die Zahlen speichern.
Andere Fall, wir können leicht beweisen, das B nicht regulär ist.
Sei B regulär , dann existiert ein FA M, die B akzeptiert. Nehmen wir k, die
Anzahl der Zustände des Automates. Wenn n mehr größe als k wäre, weil
anbn gehört zu B, es muss auch bei M akzeptiert werden kann. Weil n >> k,
bei Schubladeprinzip, es muss in einige Zustände viele mals zyklen. Jetzt
nehmen wir solche Zyklus weg, bekommen wir ein neue Wort, nennen wir w.
w kann auch bei M akzeptiert werden. Aber w gehört nicht zu B, da die
Anzahl von a und die Anzahle von b verändert sich wegen der Weglassung
von Zyklus. Und wir können auch die Zyklus als Copie einfügen, analog wie
Weglassung, dies String kann bei M akzeptiert werden, aber gehört nicht zu
B. Wiederspruch!. Deswegen, B ist nicht regulär.
Also generieren wir einen Satz: Pumpinglemma. Es ist sehr weiter benutzen,
um zu beweisen, daß eine Sprache nicht regulär ist.
Die Idee ist: wenn FA akzeptiert eine längere Wort und es länge als der
Anzahl der Zustände ist, existiert es bestimmt einen wiederholte Zustand.
Wenn die Copie dieses Segmentes eingefügt, diese neue String kann auch
bei FA akzeptiert werden.
2. Definition: reguläre Pumpingeigenschaft
Normale Form
Eine Sprache L aus Σ*
∃
∀
K∈ N
w∈L
|w| ≥ k
hat die reguläre Pumpingeigenschaft gdw
∃
∀
: uvix ∈ L
u, v, x ∈ Σ*
i∈N
w = uvx
v≠ε
|v| ≤ k
schärfere Form
∃
∀
K∈ N
w∈L
|w| ≥ k
∃
u, v, x ∈ Σ*
w = uvx
v≠ε
|v| ≤ k
|u| ≤ k
∀
i∈N
: uvix ∈ L
Jede reguläre Sprache hat die schärfere reguläre
Pumpingeigenschaft
Beweisen: Sei K=|Zustand des DFA| für reg.Sprache, w ein Wort aus L einer
Länge Größergleich k, und z der Präfix bestehend aus den ersten k Zeichen
von w, so durchläuft z einen Zustand des DFA wenigstens zweimal, dh. Es
gibt einen Teil v von z, dessen Länge kleinergleich k ist und der von einem
Zustand q wieder zu q führt. Dieser kann herausgenommen oder wiederholt
eingefügt werden, ohne das Akzeptierungsverhalten des DFA zu ändern.
Pumping Lemma: kontraform
∀
∃
∀
K∈ N
w∈L
u, v, x ∈Σ*
|w| ≥ k
w = uvx
v≠ε
|v| ≤ k
∃
i∈N
: uvix ∉ L
Üblicherweise wird dieser Satz dazu benützt, zu zeigen, daß eine Sprache
nicht regulär ist, weil sie nicht einmal die reguläre Pumpingeigenschaft hat,
nicht pumpbar ist.
3. Benutzung des Pumpinglemmas
Strategie: Sie möchten zeigen, daß A nicht regulär ist
Demon möcht zeigen, daß A regulär ist.
Dies Prozeß(wie Spiel) wie folge
1. Demo nimmt k. (wenn A wirklich regulär wäre, Demon nimmt hier
besser die k gleich die Anzahl der Zustände des zu A gehörigen DFAs)
2. Sie wählen x,y,z , suchen xyz∈A und |y| ≥ k
3. Demon wählt u,v,w, suchen y=uvw und v ≠ ε
4. Sie wählen i ≥ 0
Sie siegen, wenn xuviwz ∉ A; Demon siegt, wenn xuviwz ∈ A
Beispiel :
A = {anbm | n ≥ m }
C = { an! | n ≥ 0 }
Trick: Benutzen wir die Abschlußeigenschaft um den Beweisen zu
vereinfachen.(Komplement, Durchschnitt, Vereinigung, Homormorphismus,
usw )
4. Hinweis zur Pumpingeigenschaft
1. Jede reguläre Sprache hat die P.E.
2. Es gibt nichtreguläre Sprache mit der reguläre P.E.
5. Ultimativ periodisch
Definition: eine Menge U ⊆ N von natürlichen Zahlen heißt ultimativ
periodisch gdw. ∃ k ∈ N ∃ p ∈ N+ (∀m ∈ N mit m≥k) :
m∈U gdw
m+p ∈ U
Satz: sei A ⊆ {a}*. A ist regulär gdw. { m | am ∈ A } ist ultimativ
periodisch.
Beweis:
A ist regulär, dann exisitiert ein DFA M, die A akzeptiert. Weil M nur ein
Element hat und deterministisch ist, es hat genau nur am Ende einen Zyklus.
Sei p die Länge des Zyklus, n die Länge der Anfangsschwanz, wenn m≥n, M
akzeptiert nur am+p.
Andere Seite, sei es existiert eine ultimative periodische Menge U, p die
Länge des Zyklus, n der Startpunkt des Zyklus. Dann man kann ein Automat
erzeugen, seine Schwanzlänge ist n, und Zykluslänge ist p. Es akzeptiert nur
die Menge auf {a}*, seine Wortlänge liegt in U.
Folge: sei A irgendeine reguläre Menge auf finite Alphabet Σ,
dann A = { |x| | x∈A } ist ultimativ periodisch.
Beweis: Definieren wir ein Homomorphismus h: ∑ → {a} bei h(b)=a für alle
b∈∑. Also h(x)=a|x|, dann A gleich der Menge der Länge von h(A). H(a) ist
regulär unter Abschlusseigenschaft, bei obere Theorie, A ist ultimativ
periodisch.
Literatur:
Dexter C. Kozen „Automata and Computability“

Download Report