Siedma sada domacich uloh

Uloha 1

Pomocou konecnych automatov
dokazte, ze trieda regularnych jazykov je uzavreta na zrkadlovy obraz.

Uloha 2

Regularna gramatika G je v binarnom tvare ak jej pravidla su v tvare 
Nx{T,epsilon}N alebo Nx{T,epsilon} (teda A->aB alebo A->a, kde
a je pismeno alebo epsilon). 

Dokazte, ze pre kazdu regularnu gramatiku G existuje regularna gramatika G', 
taka ze L(G)=L(G') (teda ze binarny tvar je normalnym tvarom pre regularne gramatiky).

Uloha 3

Dokazte, ze ku kazdemu nedeterministickemu konecnemu automatu A existuje
nedeterministicky konecny automat A', ktory ma prave jeden akceptujuci stav a prave 
jeden pociatocny stav, pricom neexistuje prechod do pociatocneho stavu ani prechod z 
koncoveho stavu. Zaroven plati L(A')=L(A).

Uloha 4

(Pre sikovnejsich)
Majme regularny jazyk L. Zostrojte konecny automat pre jazyk L', taky ze 
L'={w | existuje u : wu \in L a zaroven |w|=|u|}. 
Teda neformalne je to jazyk "prvych polovic" slov z jazyka L. 
Dokazte spravnost konstrukcie.

Uloha 5

Su dane nedeterministicke konecne automaty A1 a A2. Zostrojte konecny
automat A taky, ze L(A) = Shuffle(L(A1),L(A2)).

Poznamka: Nech L ,L  su jazyky. Potom
                1  2

Shuffle(L1,L2) = { u v u v ... u v  | u u ... u je z L , v ... v  je z L },
                    1 1 2 2     k k    1 2     k      1   1     k       2

kde u , v   su slova.
     i   i

Uloha 6

Je dany L = { w | w je cislo v desiatkovej sustave delitelne 3 }.
Zostrojte konecny automat A rozpoznavajuci jazyk L, ktory ma najmensi mozny
pocet stavov. Svoju odpoved zdovodnite.

Uloha 7

Dany je nedeterministicky konecny automat A=({a,b,c},K,q0,delta,{q3,q6}),
K={q0,q1,q2,q3,q4,q5,q6}, delta funkcia je dana tabulkou:

delta   q0         q1   q2   q3   q4    q5   q6
 a      q0,q1,q4   -    -    q6   -     q6   q6,q0
 b      q0         q2   -    q3   -     -    q6
 c      q0         -    q3   q6   q5    -    q3
Zostrojte deterministicky konecny automat taky, ze L(A') = L(A).
Pouzite standardnu konstrukciu.

Uloha 8

Je dany L nad abecedou {a,b}* taky ze 
L = { w | pocet roznych vyskytov podlova abbab v slove w je parny }.
Pozor: rozne vyskyty slova abbab nemusia byt nutne dijunktne. Napr. v slove bbabbabbabbb 
sa nachadzaju dva rozne vyskyty abbab.
Zostrojte konecny automat A rozpoznavajuci jazyk L. Dokazte ze L(A)=L.