IB102 - úkol 7 - řešení
Odevzdání: 8.11.2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Rozhodnete, zda pro všechny jazyky L, K platí nasledujúci implikace. Svá rozhodnutí zduvodnete.
(a) L* je regulární =>- L je regularní
(b) (L \ K)R je regularní, K je regulární a K C L =>- L je regularní Řešeni:
(a) Neplatí. Uvazme napríklad jazyk L = {w E {a, b}* | w = wR}. Jazyk obsahuje slova a i b a proto platí L* = {a, b}*, coz je regularní jazyk. Jazyk L ale není regulární, coz by se dalo dokazat napríklad pomocí Pumping lemmatu s volbou slova anbban.
(b) Platí. Víme, ze regulírní jazyky jsou uzavreny na reverzi. Dostívame tedy, ze L \ K = ((L \ K)R)R je regulírní. Dale z inkluze K C L plyne, ze L = K U (L \ K). Jelikoz regulírní jazyky jsou uzavrene na sjednocení, jazyk L je take regularní.
IB102 - úkol 7 - řešení
Odevzdání: 8.11.2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Definujme T jako třídu všech jazyků, jejichž prefixová ekvivalence má index nejvýše 4. Platí tedy, že jazyk L patří do třídy T práve tehdy, když index ~L < 4. Odpovezte na našledující otazky a šve odpovedi zdůvodnete.
(a) Je třída T uzavřena na sjednocení?
(b) Je třída T uzavřena na přůnik?
(c) BONUS [+1 bod] Je třída T uzavřena na iteřaci?
(d) BONUS [+1 bod] Je třída T ůžavřená na pozitivní iteřaci?
Rešeni: Třída T není ůžavřená na sjednocení ani na přůnik. K důkazu štací vzít jazyky Li = {w G S* | |w| mod 3 = 0} a L2 = {w G S* | |w| mod 4 = 0}. Snadno še nahiedne, ze index ~Ll = 3 a index ~La = 4, tedy L1, L2 G T. Jejich šjednocení a přůnik jšou:
Li U L2 = {w G S* | |w| mod 3 = 0 V |w| mod 4 = 0} L1 n L2 = {w G S* | |w| mod 3 = 0 A |w| mod 4 = 0}
Snadno še oveří (např. pařalelním šynchřonním špojením automatů přo L1 a L2 a našlednou minimalizací), ze minimální DFA přo tyto jazyky mají 12 štavů, tedy ze index ~LluL2 = 12 a index ~LlnL2 = 12. Odtud tedy plyne, ze L1 U L2, L1 n L2 G T a třída T není ůžavřená na šjednocení ani na přůnik.
Reseni bonusovych otázek: Třída T není uzavřená na iteřaci ani na pozitivní iteřaci. Vezmeme ši našledující jazyk:
L = {w G S* | |w| mod 3 = 2} Zřejme index ~L = 3. Iteřace a pozitivní iteřace tohoto jazyka jšou:
L* = {e} U S2 U (S4 • S*) L+ = S2 U (S4 • S*)
L+ tedy obšahuje přáve všechna šlova delky 2 a delek od 4 váše, L* obšahuje totez, co L+, a navíc e. Snadno še oveří (opet např. šeštřojením automatu a jeho minimalizací), ze index ~L* = 5 a řovnez index ~L+ = 5.
Poznámka: Všimnete ši, ze naše přotipříklady fungují nezávišle na konkřetní abecede S.