IB102 úkol 6, příklad 1 Odevzdání: 4. 11. 2019
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, N, P, a R jsou jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
1. Pokud L je libovolný jazyk, pak {w | w ∈ L, |w| = 4} je regulární.
2. Pokud (L ∪ R) · (RR ∩ LR) není regulární, pak L není regulární nebo R není regulární.
3. Pokud N není regulární a (L∪N) je regulární a (P ∪N) je regulární, pak (L∪P) je regulární.
4. Pokud L je libovolný a K je konečný, pak (L ∩ K) ∪ (K \ L) je 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.