Deviata sada domacich uloh

Uloha 1

Pouzitim pumpovacej lemy pre regularne jazyky dokazte (dajte si zalezat na 
preciznych formulaciach), ze jazyk L = { a^{2n} | n>=0 } nie je regularny.
Pozn.: a^{2n} je "a na (dva na n-tu)" 

Uloha 2

Zostrojte nedeterministicky zasobikovy automat pre L = { a2n+3bn | n>=1 }.



ukazte priklad akceptujuceho vypoctu
dokazte spravnost konstrukcie.

Uloha 3

Zostrojte nedeterministicky zasobnikovy automat pre 

L =  { aibjck | i=j=k>=1 }
L =  { aibjck | i=j>=1 alebo j=k>=1 }

a zdovodnite spravnost konstrukcie.

Uloha 4

Zostrojte nedeterministicky zasobnikovy automat pre 

L =  { aibjcjdi | i,j>=0 }
L =  { aibjcidj | i,j>=0 }

a zdovodnite spravnost konstrukcie.

Uloha 5

Zostrojte nedeterministicky zasobnikovy automat pre 

  L = { wwR | w \in {a,b}*, #aw = 1 mod 2 }

a dokazte spravnost konstrukcie.

Uloha 6

Zostrojte nedeterministicky zasobnikovy automat pre 

  L = { wa2nbnwR | w \in {a,b}*, n>=0 }

a zdovodnite spravnost konstrukcie.

Uloha 7

Dany je konecny automat A=({a,b},K,p1,delta,{p3}), K={p1,p2,p3,p4}, delta funkcia je dana nasledovne: 
  delta(p1, a) = p2
  delta(p2, a) = p4
  delta(p2, b) = p3
  delta(p3, b) = p1
  delta(p3, a) = p4
  delta(p4, a) = p2

Zostrojte regularny vyraz pre mnoziny slov R234 a R323 pre automat A.