6.1.2012
IB102    Automaty a gramatiky
120 minut
Jméno: Místnost: Souřadnice:
UŠÍ I_L      'J    L"      I uco I_L      'J    L"       J    Lľ       J    L"      'J    C       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
O každém z následujících jazyků rozhodněte, zda je bezkontextový. Svá tvrzení Přiklad 1 dokažte. (Pro důkaz, že jazyk je bezkontextový, stačí napsat odpovídající gramatiku 50 bodů
nebo automat.)
(a) L\ = {a%Wck | i,j,k > 0, i + j = k, i < j}
(b) L2 = {aiVck \i,j,k>0, i+j = k, j < k}
Oblast strojově snímatelných informací, nezasahujte.
6.1.2012
IB102    Automaty a gramatiky
120 minut
Jméno:
Místnost:
Souřadnice:
list
E
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 ľ -j     body   ľ -j ľ -j ľ -j
D IE3H5E1B3
K zadanému konečnému automatu zkonstruujte ekvivalentní Přiklad 2
nedeterministický konečný automat bez e-kroků. 30 bodů
(Pokud nepoužijete standardní algoritmus, dokažte ekvivalenci obou automatů.)
	a	b	
-> 1	{1}	{1,4}	{5}
<- 2	{2}	{1}	{3}
<- 3	0	{2,5}	{2}
4	{1,4}	{2,4}	{1,5}
<- 5	{2,5}	0	0
Oblast strojově snímatelných informací, nezasahujte.
6.1.2012
IB102    Automaty a gramatiky
120 minut
Jméno: Místnost: Souřadnice:
3
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
Je dána gramatika g = ({S, A, B}, {a, b}, P, S), kde Příklad 3
20+15 bodů
P = { S      bAB | AB A       Ab    | ab B -> AB   | bb | e }.
(a) Zkonstruujte PDA A pro nedeterministickou syntaktickou analýzu shora dolů. Uveďte způsob akceptování.
(b) Zapište akceptující výpočet automatu A nad slovem babbab.
Oblast strojově snímatelných informací, nezasahujte.
6.1.2012
IB102    Automaty a gramatiky
120 minut
Jméno: Místnost: Souřadnice:
H
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
Napište algoritmus, který pro zadanou bezkontextovou gramatiku Q = (N, S, P, S) Přiklad 4 spočítá množinu M všech neterminálů, ze kterých lze odvodit prázdný řetězec, 40 bodů
tj. M = {A G N | A ^* e}.
Oblast strojově snímatelných informací, nezasahujte.
6.1.2012
IB102    Automaty a gramatiky
120 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
Rozhodněte, zda existují následující gramatiky. V kladném případě uveďte příklad Přiklad 5 takové gramatiky, v záporném důkaz její neexistence. 17+17 bodů
(a) Bezkontextová gramatika, která má vlastnost sebevložení, a přitom generuje konečný jazyk.
(b) Bezkontextová gramatika, která je vlastní, obsahuje levorekursivní neter-minál, a přitom generuje konečný jazyk.
Oblast strojově snímatelných informací, nezasahujte.
6.1. 2012 IB102    Automaty a gramatiky 120 minut
Jméno: Místnost: Souřadnice:
G
list   ľ  j I—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
Nechť (Q, E, 5, q0, F) je NFA s e-kroky. Příklad 6
6+15+15 bodů
(a) Napište typu funkce S.
(b) Definujte funkci De (včetně typu) a její rozšíření na množiny stavů.
(c) Definujte rozšířenou přechodovou funkci S (včetně typu).
Oblast strojově snímatelných informací, nezasahujte.
Datum:
IB102    Automaty a gramatiky
120 minut
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.