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.