IB102 úkol 6, příklad 1 Odevzdání: 29. 10. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] Nechť K, L a R jsou jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) Pokud K je konečný jazyk a L je libovolný jazyk, pak (L ∪ co−K) je regulární.
b) Pokud R je regulární a L není regulární, pak (L · R) není regulární.
c) Pokud R je regulární, pak {w | w ∈ R, #a(w) mod 3 = 1} je regulární.
d) Pokud (L \ R)∗ není regulární, pak L není regulární nebo R není regulární.
Pokud budete potřebovat, můžete v celém příkladu využívat toho, že na přednášce a cvičeních byly
ukázány některé neregulární jazyky (jejich neregularitu nemusíte znovu dokazovat). V důkazu můžete
rovněž použít znalosti o uzavřenosti třídy regulárních jazyků na operace prezentované na přednášce.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.