IB 102 — úkol 6 — řešení
Odevzdání: 7.11.2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Rozhodněte a dokažte, zda následující implikace platí:
(a) K je konečný jazyk, N je neregulární jazyk =>- co-((K fl N) U N) je regulární.
(b) K je konečný jazyk, N je neregulární jazyk =>- co-(K fl N) U N je regulární.
Řešení:
(a) Implikace neplatí. Stačí vzít K = 0 a N libovolný neregulární jazyk. Pak zřejmě co-((K fl N) U N) = co-N. Kdyby však co-N byl regulární, pak by i N = co-(co-iV) byl regulární, což není.
(b) Implikace platí. Zřejmě co-(K fl iV) D co-iV a proto co-(_ří fl iV) U iV = S*, což je regulární jazyk.
IB 102 — úkol 6 — řešení
Odevzdání: 7.11.2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [3 body] Mějme následující operaci na jazycích:
triple (L) = {w ■ w ■ w | w G L} Rozhodněte a dokažte, zda následující tvrzení platí:
(a) Třída všech regulárních jazyků je uzavřená na triple.
(b) Třída všech konečných jazyků je uzavřená na triple.
Pokud při dokazování budete o nějakém jazyce tvrdit, že není regulární, tuto skutečnost musíte rovněž dokázat.
Bonus [1 bod]: Změnila by se nějak odpověď na předchozí otázky, pokud bychom se omezili na jazyky nad jednoprvkovou abecedou? Pokud ano, jak a proč?
Řešení:
(a) Toto tvrzení neplatí. Vezměme si například jazyk L = {a}* ■ {b}. Platí
tnple(L) = {anbanbanb | n > 0}
O tomto jazyce ukážeme, že není regulární. Použijeme k tomu Myhill-Nerodovu větu. Nechť Ľ = triple(L). Mějme nekonečnou posloupnost slov Cl j Cl j Cl j • • • j Cl j • • • ^ ukážeme, že pro žádné i ^ j neplatí ď ~L, a?. Zřejmě však á1 ■ bďbďb G Ľ, zatímco ■ bďbďb (jL Ľ. Index ~L, je tedy nekonečný, proto Ľ není regulární.
(b) Toto tvrzení platí. Slov jazyka triple(L) je zřejmě právě tolik, kolik je slov jazyka L. (Formálně: existuje bijekce mezi L a triple(L) definovaná takto: f(w) = w ■ w ■ w.)
Bonus: Pokud bychom se omezili na jazyky nad jednoprvkovou abecedou, pak by se změnila odpověď v části (a). Třída všech regulárních jazyků nad jednoprvkovou abecedou je uzavřená na triple, neboť pak platí
tnple(L) = {a3n | an G L}
a k důkazu uzavřenosti pak stačí použít uzavřenost na homomorfismus h(a) = aaa.