IB102 – úkol 4, příklad 1 Odevzdání: 26. 10. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, nebo vyvraťte, že následující tvrzení jsou platná pro libovolnou
abecedu Σ.
a) K ⊆ Σ∗
je konečný a L ⊆ Σ∗
je libovolný =⇒ co−(K ∩ L) je regulární.
b) L1, L2 ⊆ Σ∗
jsou regulární =⇒ jazyk {w | w patří právě do jednoho z L1, L2} je
regulární.
c) L ⊆ Σ∗
je regulární, n ≥ 0 =⇒ jazyk {w | w ∈ L, |w| ≥ n} je regulární.
d) L ⊆ Σ∗
je regulární =⇒ jazyk {sort(w) | w ∈ L} je regulární (kde sort(w) je slovo
vzniklé seřazením písmen ve slově w, např. sort(acabc) = aabcc).
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.