3
Formale Syteme 2020 (Subject) / Pumpig Lemmas (Lesson)
- L2={a^i b^j c^k |i<j<k}. Sei L erkennbar , so muss gelten: Es gibt n0 ∈ N≥1 so, dass jedes Wort w ∈ L mit |w| ≥ n0 sich zerlegen lässt in w = xyz mit y != ε und xykz ∈ L für alle k ≥ 0. Sei w ∈ der Sprache. Da |xy| < n, muss n mindestens ein a lang sein. xy2z = xn+2i bn+1 cn+1, wobei i>1 aber xy2z !∈ von L2 -> Widerspruch
- a^p, wobei P Primzahl Sei L erkennbar , so muss gelten: Es gibt n0 ∈ N≥1 so, dass jedes Wort w ∈ L mit |w| ≥ n0 sich zerlegen lässt in w = xyz mit y != ε und xykz ∈ L für alle k ≥ 0. Sei p ein Primzahl mit p ≥ n0 Dann gilt: Sei x=1r, y=1s, and z=1t, sodass gilt : r+s+t=p. Dann xyiz=1r1si1t =1r+si+t = 1p+(i−1)s. Daraus folgt, p+(i−1)s muss ebenfalls eine Primzahl sein für alle i≥0. Es gilt jedoch, wenn i = p+1, dann folgt p+(i−1)s = p+ps=p(1+s), was keine Primzahl ist, da es durch p teilbar wäre, was der Definition einer Primzahl widerspricht.
- a^n b^n Sei L erkennbar , so muss gelten: Es gibt n0 ∈ N≥1 so, dass jedes Wort w ∈ L mit |w| ≥ n0 sich zerlegen lässt in w = xyz mit y != ε und xykz ∈ L für alle k ≥ 0. Sei w = anbn nun Element der Sprache. x = al, y = am, z = an−(l+m)bn, mit m > 1 Da |uv| < n folgt dass u und v nur aus a bestehen.Wir wählen für die Zerlegung nun i = 2 -> xy2z = al+2m+(n−(l+m)) = an+mbm Wegen m≥1, gilt uviw !∈ L1.