Lösung 04

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.