IB 102 — úkol 6, příklad 2 — řešení
Odevzdání: 29.10. 2012
Vypracoval: James Bond Skupina: MI6
UCO: 007
2. [2 body] Uvažme operaci double, která je pro jazyk L nad abecedou E definována následovně:
double(L) = {ww | w G L}. Dále uvažme operaci codoco, která je pro jazyk L nad abecedou E definována takto:
codoco(L) = co—(double(co—L)).
a) Rozhodněte a zdůvodněte, zda třída všech co—konečných jazyků (co—konečné jazyky jsou ty jejichž komplement je konečný) je uzavřená na operaci codoco.
b) Rozhodněte a zdůvodněte, zda třída všech regulárních jazyků je uzavřená na operaci codoco.
a) Tvrzení platí, třída co—konečných jazyků je uzavřená na operaci codoco.
Důkaz: Nechť L je libovolný co—konečný jazyk. Potom jeho doplněk {co—L) musí být konečný. Operace double nemění počet slov v jazyce, pouze zřetězuje stejná slova z jazyka za sebe, tedy výsledkem double(co—Ľ) je také konečný jazyk. Doplněk tohoto jazyka je tedy co-konečný jazyk co—(double(co—Ľ)\ který je výsledkem codoco(L). Z toho plyne, že třída co—konečných jazyků je uzavřená na operaci codoco.
b) Tvrzení neplatí, třída regulárních jazyků není uzavřená na operaci codoco. Důkaz: K tomu, abychom dokázali, že tvrzení neplatí, stačí najít libovolný regulární jazyk L, takový, že codoco(L) není regulární.
Příkladem takového jazyka je:
L = co-{anb | n > 0} Komplementem k tomuto jazyku je jazyk:
co-L = {anb | n > 0}
Po aplikování operace double dostáváme:
double(co-L) = {anbanb \ n > 0}
Tento jazyk je ovšem neregulární (lze snadno dokázat pomocí Pumping lemmatu, resp. Myhill-Nerodovy věty). Komplement k neregulárnímu jazyku je opět neregulární (jak bylo dokázáno na cvičeních), tedy výsledek codoco(L) je neregulární, z čehož plyne, že třída regulárních jazyků není uzavřená na operaci codoco.
Řešení