IB102 – úkol 10, příklad 2 – řešení Odevzdání: 8. 12. 2014
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 ⊆ R =⇒ L ≤m R
b) L ≤m ∅ ⇐⇒ L = ∅
Tvrzení a) neplatí. Tedy není pravda, že libovolný jazyk lze vždy redukovat na jazyk,
který je mu nadmnožinou.
Důkaz. Mějme L = HALT a R = Σ∗
, kde Σ je abeceda jazyka HALT. Předpoklad
implikace zřejmě platí, jelikož jazyk HALT je podmnožinou jazyka Σ∗
. Závěr implikace
však neplatí.
Z definice redukce dostáváme, že musí platit, že w ∈ HALT =⇒ f(w) ∈ Σ∗
. To je
však možné jedině pokud HALT = Σ∗
. Je však zřejmé, že existuje slovo (označme jej x),
které nepatří do jazyka HALT (stačí vzít TS, který vždy cyklí (Tinf ) a libovolné slovo,
například ε, pak jistě x = Tinf , ε /∈ HALT). Pak má platit f(x) /∈ Σ∗
, což není možné.
Implikace tedy neplatí pro žádnou funkci f a proto nelze sestrojit totálně vyčíslitelnou
funkci takovou, že w ∈ HALT ⇐⇒ f(w) ∈ Σ∗
a tedy HALT se neredukuje na Σ∗
.
Tvrzení b) platí. Tedy je pravda, že jediný jazyk, který lze redukovat na prázdný
jazyk, je prázdný jazyk. Pozor ale, nic nám nevynucuje, že oba jazyky jsou nad stejnou
abecedou, proto musíme uvažovat, že se abecedy mohou lišit.
Důkaz. Dokážeme zvlášť oba směry ekvivalence.
1. Směr L = ∅ =⇒ L ≤m ∅: Můžeme zvolit konstantní redukční funkci
f(w) = ε
Tedy funkci, která libovolné slovo z abecedy jazyka L zobrazí na prázdné slovo, to
je jistě slovem nad libovolnou abecedou a jistě nepatří do ∅. Tato funkce je totálně
vyčíslitelná a redukuje L na ∅, proto implikace platí.
2. Směr L ≤m ∅ =⇒ L = ∅ dokážeme sporem. Předpokládejme, že existuje L
různý od ∅ takový, že L ≤m ∅. Pak ale existuje slovo w ∈ L, a tedy musí platit
f(w) ∈ ∅, protože f je redukce. To však nemůže nastat. To je spor, a tudíž implikace
L ≤m ∅ =⇒ L = ∅ musí platit.
Dokázali jsme obě implikace, čímž jsme dokázali L ≤m ∅ ⇐⇒ L = ∅.