Lösung 04
loesung04.txt
—
Plain Text,
1 KB (1130 bytes)
Dateiinhalt
Musterloesung Blatt 4 --------------------- Aufgabe H-9: L = { 0^n1^m0^(n+m) ; n,m in N } Fuer n in N waehle wn = 0^n10^(n+1) in L. Es ist |wn| = 2n+2 >= n. Sei wn = xyz mit |xy| <= n und |y| >= 1. Dann ist x = 0^i y = 0^j und z = 0^(n-i-j)10^(n+1) fuer i,j mit i+j <= n und j >= 1. Waehle k=0, dann ist wn' = xy^kz = xz = 0^(n-j)10^(n+1) Dann ist aber wn' nicht in L, da wegen j >= 1 gilt: (n-j) + 1 <= n < n+1 Also ist nach Pumping Lemma L nicht regulaer. L = { w ; |w|_1 ist Quadratzahl } Fuer n in N waehle wn = 1^(n^2) in L. Es ist |wn| = n^2 >= n. Sei wn = xyz mit |xy| <= n und |y| >= 1. Dann ist x = 1^i y = 1^j und z = 1^(n^2-i-j) fuer i,j mit i+j <= n und j >= 1. Waehle k=2, dann ist wn' = xy^ky = xyyz = 1^(n^2+j) Dann ist aber wn' nicht in L, da n^2 < n^2 + j = |wn'|_1 (da j>=1) <= n^2 + n (da j<=n) < n^2 + 2n +1 = (n+1)^2 also liegt |wn'|_1 echt zwischen zwei aufeinander- folgenden Quadratzahlen und ist somit selbst keine Quadratzahl. Also ist nach Pumping Lemma L nicht regulaer.
Artikelaktionen