Stvrta sada domacich uloh

Ulohy 2 a 9 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do stredy 13.10 rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.

Uloha 1

Dokazte, ze regularna gramatika, ktora ma vsetky pravidla tvaru (A,C su neterminaly, b je terminal) je normalnym tvarom regularnej gramatiky (t.j. pre kazdu regularnu gramatiku existuje ekvivalentna gramatika v takomto tvare).

Uloha 2

(*odovzdavacia uloha)
Dokazte, ze bezkontextova gramatika, v ktorej vsetky pravidla obsahujuce terminal su tvaru je normalnym tvarom bezkontextovej gramatiky.

Uloha 3

Zostrojte bezkontextovu gramatiku pre jazyk 
      i j k
L = {a b c  | neplati i==j==k}

Uloha 4

Dokazte, ze frazova gramatika, ktora nema na lavej strane ziadneho pravidla terminal je normalnym tvarom frazovej gramatiky.

Uloha 5

Zostrojte regularnu gramatiku pre jazyk L: 
L = { w | pocet a vo w je delitelny 2 a pocet b je delitelny 3 }

Uloha 6

Dany je konecny automat A = ({a,b},K,q0,delta,F)
F = { q0, q3 q4},   K = {q0, q1, q2, q3, q4}

Delta funkcia je dana nasledovne: 

 delta(q0,a) = q1
 delta(q0,b) = q0
 delta(q1,a) = q4
 delta(q1,b) = q2
 delta(q2,a) = q3
 delta(q2,b) = q2
 delta(q3,a) = q4
 delta(q3,b) = q0
 delta(q4,X) = q4 pre X = a,b
Popiste jazyk rozpoznavany tymto automatom.
Ulohy 7-11:
Zostrojte konecny automat (vratane delta funkcie) pre nasledovne jazyky (ak nie je uvedene inak, nad abecedou {a,b}):

Uloha 7

L = { w | pocet a vo w je delitelny 2 a pocet b je delitelny 3 }

Uloha 8

L = { w | w obsahuje podslovo ababa }

Uloha 9

(*odovzdavacia uloha)
L = { w | 4-te pismeno od konca je b }

Uloha 10

 a) L = {w | w je pascalovsky identifikator }
 b) L = {w | w je fortranovsky identifikator }
Abecedu si vhodne zvolte (napr. ASCII), delta funkciu zapiste skratene. Pascalovsky identifikator sa sklada zo znakov A az Z, a az z, 0 az 9 a podtrhovnika _. Nesmie zacinat cifrou. Fortranovsky identifikator sa nesmie zacinat cifrou ani _, neobsahuje male pismena a ma dlzku najviac 8 znakov.

Uloha 11

L = {w | w obsahuje podslovo 'abb' a zaroven ma parny pocet pismen a }