IB102 - úkol 3 - řešení
Odevzdání: 11.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Mejme následující jazyk:
L = {w E {0,1}* | w je binární zápis sudeho Čísla a je-li #(w) sudá, pak je i #0(w) sudá}
priCemz za binarní zápis Čísla povazujeme pouze takovy zapis, která neobsahuje zbytečne levostranne nuly, tj. 0110 pro nas není binarní zapis čísla, zatímco 110 je. Sestrojte deterministická konečná automat pro jazyk L.
Řešení: Deterministická konecny automat akceptující jazyk L muze vypadat napr. takto: Nazvy stavu majá mnemotechnická váznam, krome q0 jsou vzdy tvaru Qx,y,z, kde x oznacuje paritu (sudost ci lichost) poctu znaku 0, y paritu poctu znaku 1a z oznacuje naposled ctená symbol.
IB102 - úkol 3 - řešení
Odevzdání: 11.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Mejme gramatiku G = ({S, A, B, C, D}, {a, b, c}, P, S), kde
P = {   S  —  aA | bS | cS | abB, A  —  abC I bA | cA,
B — aC | bB | cB,
C —  aD | bC | cC | e,
D — aD | bD | cD }
Jaký jazyk generuje tato gramatika? Svou odpoved' zduvodnete.
Rešeni: L(G) je jazyk vsech slov nad abecedou {a, b, c}, ktera obsahují podslovo ab a zaroveň obsahují prave dva symboly a, mnozinove se da zapsat takto
L (G) = {b, c}* • {a} • {b, c}* • {ab} • {b, c}* U {b, c}* • {ab} • {b, c}* • {a} • {b, c}*
K tomuto resení je mozno dospet nýsledující uvahou:
• Neterminal D je zbytecny, není z nej mozno odvodit zýdne slovo.
• Z neterminalu C je proto mozne odvodit prave vsechna slova ze symbolu b a c, tedy praívňe slova z {b, c}*.
• Z neterminíalu B je proto moňzníe odvodit príavňe slova, ktería obsahujíí praívňe jeden symbol a a libovolný pocet symbolu b a c, tedy prýve slova z {b, c}* • {a} • {b, c}*.
• Podobne z neterminýlu A je mozne odvodit prýve slova z {b, c}* • {ab} • {b, c}*.
Z predchozích dvou bodu a pravidel pro S pak zrejme vyplýva resení.