IB005 úkol 6, příklad 1 Odevzdání: 4. 4. 2022 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 M jsou libovolné jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) {a|w| | w ∈ L} je regulární =⇒ L je regulární.
b) L a M jsou regulární =⇒ {u ∈ Σ∗ | u ∈ L ⇐⇒ u ̸∈ M} je regulární.
c) L není regulární =⇒ (co−L)R není regulární.
d) Existuje binární operace ⊙ taková, že platí: L a M jsou regulární =⇒ L ⊙ M 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.