30.10.2014
IB102    Automaty, gramatiky a složitost
Čas: 90 minut
Jméno: Místnost: Souřadnice:
UŠÍ I_L      'J    L"      I UCO I_L      'J    L"       J    L"       J    L"      'J    Lľ       J    L"      'J    L"       J boďfj C       J    Ľ      'J    L" J
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
U 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
list   ľ  j I— učo   ľ  j ľ  j l  j ľ  j l  j l  j ľ  j body
Oblast strojově snímatelných informací. Své UCO 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 L   je regulární L je regulární
(b) in 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
lÍst I_L      'J UCO ľ      'J    ľ       J    L"       J    L"      'J    L"       J    Lľ      'J    L"       J boďy C      JJ    ľ      'J    L" J
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
U IE3H5E1B3
Rozhodněte, zda je jazyk Přiklad 5
9 bodů
L = {atbjck \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
body   ĺ  j ľ  j ľ j
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.
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, dokažte ekvivalenci 10 bodů
obou automatů.)
A	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:
5
list   ľ  j bJ učo   ľ  j ľ  j l  j ľ  j l  j l  j ľ  j body
Oblast strojově snímatelných informací. Své UCO 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:
list   ľ -j ľ -j učo   ľ -j ľ -j ľ -j ľ -j ľ -j ľ -j ľ -j body
Oblast strojově snímatelných informací. Své UCO 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.