7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
r.     n   r.     n   r.     n   r.     n   r.     n   r.     n   r.     n                             r.     n   r.     n   r.     n
Vl/Sv          l_T        J_l     l_L       1                            UCO          Lľ        J_l     Ľ"        J_l     L"       'J     Lľ       J_l     Ľ"        J_l     L"       'J      L"       J_l              OO&U          Lľ        J_l     l_L       '_l     L"       '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.
O každém z následujících jazyků rozhodněte, zda je hezkontextový. Svá tvrzení        Přiklad 1 dokažte. (Pro důkaz, že jazyk je hezkontextový, stačí napsat odpovídající gramatiku             50 bodů
nebo automat.)
(a)   L1 = {w e {a, b, c}* | #a(w) + #b(w) < #c(w)}
(b)   L2 = {we {a,b,c}* | #a(w) < #b(w) < #cM}
Oblast strojově snímatelných informací, nezasahujte.
7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:
Místnost:
Souřadnice:
list
E
r,     _n   r.     _n   r     .n   r,     .n   r.     _n   r     .n   r     .n
r.     .n   r.     n   r     .n
UCO
body
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íiaaHBEnsg
Je dán automat A:
Příklad 2
30 bodů
Napište regulární výraz E popisující jazyk L(A).
(Rovnost L(E)  = L(A) nemusíte dokazovat, pokud použijete standardní algoritmus a zakreslíte
všechny jeho mezivýsledky.)
Oblast strojově snímatelných informací, nezasahujte.
7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
3
r.     n   r.     n   r.     n   r,     .n   r.     .n   r.     n   r.     .n                             r.     n   r.     n   r.     n
Vl/Sv         l_T        J_l     ^H^J                         UCO         Lľ        J_l     Ľ"        J_l     L"      'J     Lľ      J_l     Ľ"        J_l     L"      'J      L"      J_l             OO&U         Lľ        J_l     l_L      '_l     L"      '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.
Je dána gramatika Q = ({S, A, B}, {a, b, c}, P, S), kde                                               Příklad 3
35 bodů
P = { S  -»■ ab      |  Ab
A  -► BaA   j  Sc  |   Ac B  ^ AA     \  bB   }.
Převeďte gramatiku Q na ekvivalentní nelevorekursivní bezkontextovou gramatiku. Pokud nepoužijete algoritmus z přednášky, dokažte ekvivalenci výsledné gramatiky s gramatikou ze zadání.
Oblast strojově snímatelných informací, nezasahujte.
7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
H
r,     n   r.     n   r.     n   r,     n   r.     n   r.     n   r.     .n                        r.     n   r.     n   r.     n
Vl/Sv         l_T        J_l     l_L       1                          UCO         Lľ        J_l     Ľ"        J_l     L"       'J     Lľ       J_l     Ľ"        J_l     L"       'J      L"       J_l             OOďtJ         Lľ        J_l     l_L       '_l     L"       '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.
Napište algoritmus, který pro zadanou redukovanou bezkontextovou gramatiku        Přiklad 4 Q = (N,T,,P,S) spočítá množinu M všech neterminálů, z kterých lze odvodit             40 bodů
neprázdný řetězec, tj. M = {A G N \ A =>* w pro nějaké w G S+}.
Oblast strojově snímatelných informací, nezasahujte.
7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
B
r,     n   r.     n   r.     n   r,     n   r.     n   r.     n   r.     .n                             r.     n   r.     n   r.     n
Vl/Sv         l_T        J_l     ^H^J                         UCO         Lľ        J_l     Ľ"        J_l     L"      'J     Lľ      J_l     Ľ"        J_l     L"      'J      L"      J_l             OO&U         Lľ        J_l     l_L      '_l     L"      '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.
Rozhodněte, zda existují následující gramatiky. V kladném případě uveďte příklad       Příklad 5 takové gramatiky, v záporném důkaz její neexistence.                                                15+15 bodů
(a)  Regulární gramatika, která je zároveň bezkontextovou gramatikou v CNF.
(b)  Bezkontextová gramatika v GNF, která je cyklická.
Oblast strojově snímatelných informací, nezasahujte.
7.1.2010
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
E
r,     n   r.     n   r.     n   r,     n   r.     n   r.     n   r.     .n                             r.     n   r.     n   r.     n
Vl/Sv         l_T        J_l     ^H^J                         UCO         Lľ        J_l     Ľ"        J_l     L"      'J     Lľ      J_l     Ľ"        J_l     L"      'J      L"      J_l             OO&U         Lľ        J_l     l_L      '_l     L"      '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.
Příklad 6
(a)  Definujte pojmy gramatika a kontextová gramatika.                                          30+10 bodů
(b)  Definujte, kdy má bezkontextová gramatika vlastnost sebevložení.
Oblast strojově snímatelných informací, nezasahujte.
Datum:
IB102     Automaty a gramatiky
120 minut
Jméno:                                                             Místnost:                      Souřadnice:
r.     n   r.     n                                    r,     n   r.     n   r.     n   r.     n   r.     n   r.     n   r.     n                             r.     n   r.     n   r.     n
h%Sv          Lľ        J_l     l_L       'J                           UCO          Lľ        J_l     Ľ"        J_l     L"       'J     L"       J_l     Ľ"        J_l     L"       'J      L"       J_l             OO&U          Lľ        J_l     l_L       '_l     L"       '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.
Oblast strojově snímatelných informací, nezasahujte.