IB005 úkol 6, příklad 1 Odevzdání: 1. 4. 2024 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, R a K jsou libovolné jazyky nad abecedou Σ = {a, b, c}. Jazyk nazýváme
kokonečný, právě když je doplňkem konečného jazyka. Operace ∆ se nazývá symetrický rozdíl a je
definována jako L∆R = (L \ R) ∪ (R \ L).
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) co−K ∪ (L · RR) není regulární =⇒ L není regulární nebo co−R není regulární nebo K není
kokonečný.
b) L je regulární =⇒ jazyk W = {u ∈ Σ∗ | u ∈ L a u začíná na znak a} je regulární.
c) L je nekonečný regulární =⇒ (L · LR) ∩ (LR · L) je konečný.
d) L je regulární a R je regulární =⇒ L∆R 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ůkazech tvrzení
a), b) a c) můžete rovněž použít znalosti o uzavřenosti třídy regulárních jazyků na operace
prezentované na přednášce. V důkazu tvrzení d) není povoleno použít uzávěrové vlastnosti regulárních
jazyků, můžete však využít tvrzení (2.1) z důkazu věty (2.10) ze skript.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.