15.11.2011
IB102    Automaty a gramatiky
Čas: 90 minut
Jméno: Místnost: Souřadnice:
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
Definujte následující operace nad jazyky: zřetězení a i-tá mocnina {i g No). Příklad 1
V definicích nepoužívejte notaci s nepřesným významem (typicky "..."). 8 bodů
Dále definujte, kdy je třída jazyků C uzavřená na binární operaci o.
Určete, kolik slov má jazyk L* \ (L2) + , kde L = {aa, aaa}. Všechna slova vypište.       Přiklad 2
5 bodů
Oblast strojově snímatelných informací, nezasahujte.
15.11.2011
IB102    Automaty a gramatiky
Č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
10 bodů
L = {w £ {0,1}* | w končí podslovem 0101}.
Rozhodněte, zda platí následující implikace. Svá rozhodnutí zdůvodněte. Přiklad 4
10 bodů
(a) K je konečný a L není regulární   ==?■   K* U L není regulární
(b) K je konečný a K* U L není regulární   ==ŕ   L není regulární
Oblast strojově snímatelných informací, nezasahujte.
15.11.2011
IB102    Automaty a gramatiky
Čas: 90 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
Rozhodněte, zda je jazyk Přiklad 5
15 bodů
L = {w g {a, b, c}* | #b(w) = #a{w) v #a(w) mod 2 = 1} 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.
15.11.2011
IB102    Automaty a gramatiky
Čas: 90 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
Zkonstruujte konečný automat rozpoznávající jazyk popsaný regulárním výrazem Přiklad 6 (6*.(0.c))*.(a.a + e). (Nemusíte dokazovat, že zkonstruovaný automat rozpoznává 12 bodů
zadaný jazyk, pokud použijete standardní algoritmus a uvedete i jeho mezivýsledky. Při provádění algoritmu můžete vykonat více kroků naráz, bude-li se každý krok týkat jiného přechodu.)
Oblast strojově snímatelných informací, nezasahujte.
15.11.2011 IB102    Automaty a gramatiky Čas: 90 minut
Jméno: Místnost: Souřadnice:
5
Ust I_L      'J UCO U      '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.
D IE3H5E1B3
Uvažujme jazyk L = {a}.{a,b}*.{a} nad abecedou £ = {a, b}. Přiklad T
15 bodů
• Určete index
Popište jednotlivé třídy rozkladu £*/
Zadefinujte jazyk Ľ nad abecedou £ takový, že Ľ / L a ~ľ=~l-
Oblast strojově snímatelných informací, nezasahujte.
Náhradní list
IB102    Automaty a gramatiky
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.