IB 102 - úkol 2 - řešení
Odevzdání: 10.10. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Mějme následující jazyk:
L = {w G {k, o, s}* I w neobsahuje podslovo kokos ani podslovo koks}
Sestrojte totální deterministický konečný automat přijímající jazyk L.
Varianta za 1 bod: Pokud toto zadání nezvládnete, zkuste sestrojit automat pro jazyk všech slov nad abecedou {k,o, s} neobsahujících pouze podslovo kokos.
Řešení: Totální deterministický konečný automat přijímající L může vypadat například takto:
o
Poznámka: Řešení varianty za 1 bod by mohlo vypadat obdobně, jen by v automatu neexistoval stav qkoks a přechod pod s ze stavu q^ok by vedl do stavu q£.
IB 102 - úkol 2 - řešení
Odevzdání: 10.10. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Mějme následující gramatiku (nemusí být regulární) s vynechanou částí pravidel:
G = ({S, A, B, C, D, E, F}, {0,1}, P, S)
p = { S -+ 0\1A, A —ř OB \ 1C, B -> OD | 1E, C -+ OF | 1A, D —ř OB \ 1C, E —ř OD \ 1E, F  -+  ??? }
Doplňte do gramatiky pravidla pro neterminál F tak, aby gramatika generovala jazyk
L = {w G {0,1}* | w je binárni zápis čísla dělitelného 6}.
Své řešení zdůvodněte.
Nápověda: Je třeba přidat tři pravidla.
Řešení: Do gramatiky přidáme pravidla F —> OF | 1A | e.
Zdůvodněni: Libovolná větná forma odvozená z S v této gramatice je buď S nebo 0 nebo tvaru wX, kde w G {1} • {0,1}* a X G {A, B, C, D, E, F}. Pro každou větnou formu tvaru wX platí:
• je-li X = A, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 1,
• je-li X = B, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 2,
• je-li X = C, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 3,
• je-li X = D, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 4,
• je-li X = E, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 5,
• je-li X = F, pak w je binární zápis čísla, jehož zbytek po dělení 6 je 0.
Toto tvrzení by se dalo snadno dokázat indukcí k délce w. Spolu s existencí pravidla F —> e z toho vyplývá, že gramatika generuje zadaný jazyk L.