IB102 – úkol 4, příklad 1 – řešení 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.
a) Tvrzení platí.
Důkaz. Nechť K je libovolný konečný jazyk a L je libovolný jazyk. Pak i jazyk
K ∩ L je konečný. Jelikož K ∩ L je konečný, tak je i regulární a z uzavřenosti třídy
regulárních jazyků na doplněk plyne, že i co−(K ∩ L) je regulární.
b) Tvrzení platí.
Důkaz. Jazyk L = {w | w patří právě do jednoho z L1, L2} můžeme vyjádřit jako
(L1 ∪ L2) \ (L1 ∩ L2). Jelikož je třída regulárních jazyků uzavřená na operace ∪, ∩
a \, tak je i L regulární.
c) Tvrzení platí.
Důkaz. Mějme jazyk R = {w | w ∈ Σ∗
, |w| ≥ n} = Σn
·Σ∗
. Jazyk R je regulární což
vyplývá z uzavřenosti třídy regulárních jazyků na operace mocnina a iterace. Pak
můžeme jazyk {w | w ∈ L, |w| ≥ n} vyjádřit jako L ∩ R. Jelikož je třída regulárních
jazyků uzavřená na operace ∩, tak je i jazyk {w | w ∈ L, |w| ≥ n}.
d) Tvrzení neplatí.
Důkaz. Dokážeme protipříkladem. Mějme regulární jazyk L = {w | w = (ab)n
, n ∈
N}, pak jazyk {sort(w) | w ∈ L} = {w | w = an
bn
, n ∈ N} o kterém z přednášky
víme, že není regulární.