IB102 - úkol 6
Odevzdání: 7.11.2011
Vypracoval (a): UČO: Skupina:
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 A^) U N je regulární.
IB 102 - úkol 6
Odevzdání: 7.11.2011
Vypracoval (a): Skupina:
UCO:
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č?