30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
r.    ,n  rr    ,n  r.    ,n  r.    ,n  rr    ,n  r.    ,n  r.    ,n rr    ,n  rr    ,n  r. ,n
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Definujte množinu regulárních výrazů nad abecedou S a pro každý regulární Přiklad 1
výraz E definujte jazyk L{E) jednoznačně určený výrazem E. 6 bodů
Určete, kolik slov má jazyk (LR.L.LR) \ L*, kde L = {a, ab}. Příklad 2
Všechna slova vypište. 3 body
Oblast strojově snímatelných informací, nezasahujte.
30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
E
r.    ,n  r;    ,n  r.    ,n  r.    ,n  r;    ,n  r.    ,n  r.    ,n r;    ,n  rr    ,n  r. ,n
iisí   ľ u l—a nčo   ľ u ľ u ĺ- -j ľ -_i ľ u ĺ- -j ĺ- -_i body
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Navrhněte deterministický konečný automat, který rozpoznává jazyk Přiklad 3
6 bodů
L = {w G {a, b}* | (#a(w) mod 2) + (#b(w) mod 4) = 3}.
Rozhodněte, zda platí následující implikace. Svá rozhodnutí zdůvodněte. Přiklad 4
8 bodů
(a) L n LH je regulární   ==>■   L je regulární
(b) L n LR není regulární   ==>■   L není regulární
Oblast strojově snímatelných informací, nezasahujte.
30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
3
r.    ,n  rr    ,n  r.    ,n  r.    ,n  rr    ,n  r.    ,n  r.    ,n rr    ,n  rr    ,n  r. ,n
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Rozhodněte, zda je jazyk Přiklad 5
9 bodů
L = {aib>ck | i, j, k > 0, i ■ j > k} regulární. Své tvrzení dokažte.
(Pro důkaz, že jazyk je regulární, stačí napsat odpovídající gramatiku nebo automat.)
Oblast strojově snímatelných informací, nezasahujte.
30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno:
Místnost:
Souřadnice:
list
H
r.    ,~i  rr    ,~i  r.    .n  r.    ,n  rr    ,~i  r.    .n  r. ,n
rr    ,~i  rr    .n  r. .n
Oblast strojově snímatelných informací. Své U ČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
■j l- -_i    body   c u ll -j ĺ- -j
D IE3H5E1B3
K danému konečnému automatu A sestrojte ekvivalentní nedeterministický konečný Přiklad 6 automat bez e-kroků. (Nepoužijete-li standardní algoritmus, dokážte ekvivalenci 10 bodů
obou automatu.)
Á	a	b	
-> 1	{5}	{1}	{2}
<- 2	0	{2}	0
3	{2}	{3,5}	{1}
4	{3}	{2,4}	{1,5}
5	{4}	{1,2,5}	0
Oblast strojově snímatelných informací, nezasahujte.
30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
E
r.    ,n  r;    ,n  r.    ,n  r.    ,n  r;    ,n  r.    ,n  r.    ,n r;    ,n  rr    ,n  r. ,n
iisí   l  j _J nčo   ľ  j l  j ĺ-  j c -_i l  j ĺ-  j ĺ- -_i body
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Pro jazyk L = {w £ {a, b}* \ w začíná i končí na a a #b(w) Je sudý} sestrojte Přiklad T
8 bodů
(a) regulární výraz, který ho popisuje,
(b) regulární gramatiku, která ho generuje.
Oblast strojově snímatelných informací, nezasahujte.
Náhradní list IB102    Automaty, gramatiky a složitost
Jméno: Místnost: Souřadnice:
říSÍ Ľ      U    LL      "J ttČO L.'      U    Ľ      U    L'      'J    Ľ      "J    Ľ      U    L'      "j    Ľ      "_l boďl/
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Oblast strojově snímatelných informací, nezasahujte.