IB005 úkol 6, příklad 1 Odevzdání: 3. 4. 2020 12:00
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. [0,5 bodu] Nechť L a R jsou jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) (R \ L) ∩ ((L \ R)R) není regulární =⇒ L není regulární nebo R není regulární.
b) L je regulární =⇒ jazyk W = {u ∈ Σ∗ | u ∈ L nebo u začíná na znak a} je regulární.
c) L je nekonečný regulární a R · L je regulární =⇒ R je regulární nebo R obsahuje ε.
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.