IB005 úkol 6, příklad 1 Odevzdání: 11. 4. 2021 23:59
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ť V , L a K jsou jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) L je regulární =⇒ jazyk WL = {axbycz | ∃w ∈ L. x = #a(w) ∧ y = #b(w) ∧ z = #c(w)} je
regulární.
b) (KR ∩ L)∗ ∪ (K \ L∗) není regulární a L je nekonečný =⇒ K je nekonečný.
c) L je nekonečný a K je konečný =⇒ (co−L ∩ K) ∪ (co−K ∪ L) je regulární.
d) V není regulární nebo L není regulární nebo K není regulární nebo co−((V · {a}∗) ∩ (L \ K)) 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.