IB102 - úkol 2
Odevzdání: 10.10. 2011
Vypracoval (a): UČO: Skupina:
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.
IB102 - úkol 2
Odevzdání: 10.10. 2011
Vypracoval (a): UČO: Skupina:
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.