IB102 - úkol 1 - řešení                                    Odevzdání: 12.10. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
1. [2 body] Popište jazyk generovaný gramatikou G = ({S, A, B, C}, {a, b}, P, S), kde
P = {  S -»■ aA\bB\a\b, A -> aA\bC\a, B ->■ aB\bB\b, C -> aC\bA\b  }
Je tento jazyk regulárni?
Řešení:
Z neterminálu B lze odvodit všechny slova nad abecedou {a, b} končící znakem b. Z neter-minálu A lze postupně odvodit právě slova obsahující sudý počet znaků b (s výjimkou prázdneho slova). Zapojením kořenového neterminálu S tedy zistíme, že slovo z jazyka generovaného gramatikou G začíná znakem a a obsahuje sudý počet znaků b, nebo začíná a končí právě znakem b.
Jazyk je regulární, protože existuje regulární gramatika, která ho generuje - je to například gramatika G ze zadání.
IB102 - úkol 2 - řešení                                    Odevzdání: 12.10. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
2. [2 body] Sestrojte deterministický konečný automat akceptující jazyk:
L = {w E {a, b, c}* | (#a(u>) + 2^b{w) + 3#c(w)) mod 4 = 3 A w obsahuje znak c}
Řešení:
Vysvětlení:
Automat je ve stavu cii nebo a,itC právě tehdy, když (#a(u>) + 2#b(w) + 3#c(w)) moc? 4 = i Automat přejde ze stavu a» do stavu aJ)C, kde j = (i + 3) moc? 4, právě při prvním výskytu znaku c. Stav a3;C je proto akceptující.