IB102 – úkol 10, příklad 2 – řešení Odevzdání: 14. 12. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ je libovolná abeceda a L, R ⊆ Σ∗
jsou libovolné jazyky nad touto
abecedou. O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení
dokažte:
a) L ≤m R a L není triviální =⇒ R není triviální
b) L ≤m R a R ≤m L =⇒ L = R
Připomeňme, že jazyk nad abecedou Σ je triviální, jestliže je roven ∅ nebo Σ∗
.
a) Tvrzení platí.
Důkaz. Nechť L, R jsou libovolné jazyky splňující předpoklad (tedy L ≤m R a L
není triviální). Z netriviality jazyka L plyne existence slov w ∈ L, w /∈ L. Neboť
L ≤m R, tak existuje funkce f : Σ∗
→ Σ∗
taková, že pro každé x ∈ Σ∗
platí
x ∈ L ⇔ f(x) ∈ R. Tedy platí f(w) ∈ R a f(w) /∈ R. Zřejmě tedy R = ∅
(neboť obsahuje slovo f(w)) a R = Σ∗
(neboť neobsahuje slovo f(w)). Tedy R není
triviální.
b) Tvrzení neplatí a vyvrátíme jej protipříkladem.
Důkaz. Nechť Σ = {a, b}, L = {a} a R = {b}. Ukážeme, že L ≤m R, R ≤m L, ale
zřejmě L = R.
Definujme funkci f : Σ∗
→ Σ∗
následovně:
f(w) =
b, jestliže w = a,
bb jinak
Ukážeme, že f je redukcí z L do R.
Buď w ∈ Σ∗
libovolné. Platí w ∈ L ⇔ w = a ⇔ f(w) = b ⇔ f(w) ∈ R. Funkce f
je zřejmě totálně vyčíslitelná. Tedy platí, že L ≤m R.
Nyní uvažme funkci f : Σ∗
→ Σ∗
, kde
f (w) =
a, jestliže w = b,
aa jinak
Ukážeme, že f je redukcí z R do L.
Buď w ∈ Σ∗
libovolné. Platí w ∈ R ⇔ w = b ⇔ f (w) = a ⇔ f (w) ∈ L. Funkce f
je totálně vyčíslitelná, a tedy R ≤m L.
Tvrzení tedy neplatí, neboť jsme nalezli dva jazyky takové, že L ≤m R, R ≤m L a
zároveň L = R.