IB102 - úkol 6, příklad 2
Odevzdání: 29.10. 2012
Vypracoval (a): Skupina:
UCO:
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.
(Pozn. U jazyků ze sbírky příkladů nebo z přednášky, o kterých bylo dokázáno, že nejsou regulární, není potřeba neregularitu znovu dokazovat.)