Siesta sada domacich uloh

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

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.

Uloha 1

Dokazte, ze nedeterministicke konecne automaty s pociatocnym stavom, do ktoreho neexistuje ziadny delta-prechod a s jedinym koncovym stavom, z ktoreho neexistuje ziadny delta-prechod,su normalnym tvarom pre konecne automaty.

Uloha 2

Dany je nedeterministicky konecny automat A = (K,{a,b},delta,q₀,{q₂, q₄})
K = {q₀, q₁, ..., q₅}

Delta funkcia je dana nasledovne:

 delta(q₀,epsilon) = { q₁, q₅ }
 delta(q₀,b) = { q₂ }
 delta(q₁,a) = { q₀ }
 delta(q₁,b) = { q₂ }
 delta(q₁,epsilon) = { q₃ }
 delta(q₂,a) = { q₃ }
 delta(q₃,a) = { q₅ }
 delta(q₃,epsilon) = { q₄ }
 delta(q₄,a) = { q₃ }
 delta(q₄,b) = { q₁ }
 delta(q₅,epsilon) = { q₄ }
 delta(q₅,a) = { q₁ }

Zostrojte ekvivalentny konecny automat bez epsilonovych prechodov.

Uloha 3

Dany je nedeterministicky konecny automat A = (K,{a,b},delta,q₀,F)
F = { q₀, q₄ }, K = { q₀, q₁, ..., q₄}

Delta funkcia je dana nasledovne:

 delta(q₀,a) = { q₁, q₃ }
 delta(q₀,b) = { q₂, q₄ }
 delta(q₁,a) = { q₂ }
 delta(q₂,b) = { q₃ }
 delta(q₃,a) = { q₀ }
 delta(q₃,b) = { q₁, q₄ }
 delta(q₄,a) = { q₀ }

Zostrojte deterministicky konecny automat A' taky, ze L(A') = L(A).

Uloha 4

Ku automatu z ulohy 3 zostrojte regularnu gramatiku G generujucu ten isty jazyk.

Uloha 5

Dany je regularny jazyk L. Dokazte, ze aj jazyk L^R (reverz jazyka L) je regularny.

Ulohy 6-8:
Zistite, ci su nasledujuce jazyky regularne. Ak ano, zostrojte pre ne konecny automat alebo regularnu gramatiku, ak nie, dokazte.

Uloha 6

       p
L = { a  | p je prvocislo }

Uloha 7

(* odovzdavacia uloha)

       z
L = { a  | z je zlozene cislo }

Uloha 8

L = { w | w je nad abecedou {a,b} a v ziadnom prefixe 
                 w nie je viac b-cok ako a-cok }

Ulohy 9-10:
Zostrojte konecny automat rozpoznavajuci jazyk

Uloha 9

L = { w | w je nad abecedou {a,b} a pocet a-cok vo w 
      je parny a tretie pismeno od zaciatku je rovnake ako sieste 
      pismeno od konca }

Uloha 10

L = { w | w je cislo v desiatkovej sustave delitelne 7 }

Uloha 11

(* odovzdavacia uloha) Zostrojte bezkontextovu gramatiku pre jazyk

L = { w | w je nad abecedou {a,b} a pocet a-cok vo w 
                 je rovnaky ako pocet b-cok vo w }

Nezabudnite uviest dokaz.

Uloha 12

Dokazte, ze prienik dvoch regularnych jazykov je opat regularny jazyk. Pouzite Myhill-Nerode vetu.