IB102 úkol 11, příklad 2 Odevzdání: 12. 12. 2016
Jméno: UČO: Skupina:
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.
2. [2 body] Nechť Σ je libovolná abeceda a A, B, C, D ⊆ Σ∗ 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) A ≤m {a} ⇐⇒ A je rekurzivní
b) A ≤m B a C ≤m D =⇒ A ∩ C ≤m B ∩ D
a) Tvrzení platí.
Důkaz. Nejprve dokážeme směr A ≤m {a} =⇒ A je rekurzivní:
Jazyk {a} je konečným jazykem nad nějakou abecedou Φ (obsahující písmeno a). Tento jazyk
je tedy regulární, proto i rekurzivní. Pokud se A redukuje na jazyk, který je rekurzivní, pak i
A musí být rekurzivní (viz slajdy 10 z přednášky).
Směr A je rekurzivní =⇒ A ≤m {a}:
Definujme funkci f : Σ∗ → Φ∗ následovně:
f(w) =
a, jestliže w ∈ A,
aa jinak
Ukážeme, že f je redukcí z A do {a}.
Buď w ∈ Σ∗ libovolné. Platí w ∈ A ⇔ f(w) = a ⇔ f(w) ∈ {a}. Jazyk A je rekurzivní, takže
funkce f je totálně vyčíslitelná (pro vypočítání f stačí modifikovat TM rozhodující A tak, aby
místo přechodu do qacc zapsal na pásku a a místo přechodu do qrej zapsal na pásku aa). Tedy
platí, že A ≤m {a}.
Dokázali jsme obě implikace, a tedy že A ≤m {a} ⇐⇒ A je rekurzivní.
b) Tvrzení neplatí a vyvrátíme jej protipříkladem.
Důkaz. Zvolíme A = B = C = {a} a D = {b} nad abecedou Σ = {a, b}.
Platí, že A ≤m B, kde funkce f : Σ∗ → Σ∗ je identita. Tato funkce je jistě redukcí z A do B a
je totálně vyčíslitelná.
Platí i C ≤m D:
Definujme funkci f : Σ∗ → Σ∗ následovně:
f(w) =
b, jestliže w = a,
bb jinak
Ukážeme, že f je redukcí z C do D.
Buď w ∈ Σ∗ libovolné. Platí w ∈ C ⇔ w = a ⇔ f(w) = b ⇔ f(w) ∈ D. Funkce f je zřejmě
totálně vyčíslitelná. Tedy platí, že C ≤m D.
Nyní však neplatí A ∩ C ≤m B ∩ D, neboli {a} ≤m ∅. Kdyby platilo {a} ≤m ∅, tak by podle
definice redukce a toho, že a ∈ {a}, existovala funkce f taková, že f(a) ∈ ∅, to ale není možné.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.