Siedma sada domacich uloh
Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na
riesenie danej ulohy, pouzivajte ju.
Uloha 1
Dany je nedeterministicky konecny automat
A = (K,{a,b},delta,q0,{q2})
K = {q0, q1, q2}
Delta funkcia je dana nasledovne:
delta(q0,a) = { q1 }
delta(q1,b) = { q2 }
delta(q2,a) = { q1 }
delta(q2,b) = { q0 }
Zostrojte regularny vyraz pre jazyk L(A) (pomocou mnozin Ri,jk
z dokazu Kleeneho vety).
Ulohy 2-5:
Pomocou regularnych gramatik dokazte, ze ak L1 a L2
su regularne jazyky, tak aj nasledovne jazyky su regularne:
Uloha 2
L1 zjednotenie L2
Uloha 3
L1*
Uloha 4
h(L1), kde h je lubovolny homomorfizmus.
Ulohy 5-7:
Pomocou Myhill-Nerodovej vety dokazte, ze ak L1 a L2
su regularne jazyky, tak aj nasledovne jazyky su regularne:
Uloha 5
L1 zjednotenie L2
Uloha 6
h(L1), kde h je lubovolny homomorfizmus.
Uloha 7
(L1)C, t.j. komplement jazyka L1
Ulohy 8-9:
Definujte nasledujuce modifikacie konecneho automatu (standardne 4
definicie) a dokazte ekvivalentnost s konecnymi automatmi.
Uloha 8
Konecny automat s pruznou hlavou (nedeterministicky). Hlava konecneho
automatu cita vzdy
maximalne jedno pismeno z pasky. Pruzna hlava vie citat aj viacero za sebou
nasledujucich pismen naraz.
Uloha 9
Konecny automat s dodatocnou podmienkou taky, ze pre kazdy stav q plati:
vsetky prechody do q su na rovnake pismeno (alebo vsetky su na epsilon).
Uloha 10
Nech R je lubovolna relacia na abecede Sigma. Dokazte, ze jazyk
pozostavajuci zo slov, v ktorych lubovolne dve po sebe iduce pismena su v
relacii R, je regularny.