IB102 – úkol 9, příklad 2 – řešení Odevzdání: 1. 12. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ = {a, b} je abeceda a L1, L2 ⊆ Σ∗
jsou 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) co−L1 ∪ L∗
2 není bezkontextový ⇒ L1 není deterministický bezkontextový nebo L2
není bezkontextový
b) L1 je bezkontextový a L2 je rekursivně spočetný ⇒ L1 \ L2 je rekursivně spočetný
c) L1 je rekursivní ⇒ {w | abba.w ∈ L1} je rekursivní
Pokud se rozhodnete podat konstruktivní důkaz, nemusíte uvádět technické detaily konstrukce
(tedy nemusíte podrobně krok po kroku popisovat algoritmus transformace). Postačí
popsat ideu tak, aby bylo dostatečně jasné, jak vaše konstrukce funguje. Nejste však
zbaveni povinnosti se přesně a formálně vyjadřovat. Formulace, u nichž nebude jasná
interpretace, nebudou uznávány.
a) Tvrzení platí. Dokážeme obměnou. Tedy podáme důkaz následujícího tvrzení: L1 je
deterministický bezkontextový jazyk a zároveň L2 je bezkontextový jazyk ⇒ co−L1∪L∗
2
je bezkontextový jazyk.
Platnost tohoto tvrzení plyne přímo z uzávěrových vlastností. Třída DCFL je uzavřená
na doplněk, tedy je-li L1 DCFL, pak je i co−L1 DCFL (a tedy i CFL). Jazyk L2
je CFL a z uzavřenosti bezkontextových jazyků na iteraci plyne, že i L∗
2 je CFL.
Sjednocením dvouch bezkontextových jazyků dostáváme opět z uzávěrových vlastností
bezkontextový jazyk, a tedy tvrzení platí.
b) Tvrzení neplatí. Vyvrátíme jej protipříkladem. Uvažme například jazyk L1 = Σ∗
a
L2 = HALT. Pak L1 je zřejmě bezkontextový jazyk a o L2 bylo ukázáno na přednášce,
že je rekursivně spočetný. Jejich rozdílem L1 \ L2 je jazyk co−HALT, o kterém bylo
dokázáno, že není rekursivně spočetný. Implikace tedy neplatí.
c) Tvrzení platí. Podáme konstruktivní důkaz. Neboť je jazyk L1 rekursivní, existuje
úplný Turingův stroj M, který jej akceptuje. Tohoto stroje využijeme ke konstrukci
úplného Turingova stroje M akceptujícího {w | abba.w ∈ L1}.
Stroj M bude pracovat na libovolném vstupním slově u následovně:
1) Doplň před slovo u řetězec abba.
2) Simuluj Turingův stroj M na tomto slově (tedy na slově abba.u).
3) Akceptuje-li M, akceptuj. V případě, že M zamítá, zamítni také.
IB102 – úkol 9, příklad 2 – řešení Odevzdání: 1. 12. 2014
Vypracoval(a): UČO:
Skupina:
Snadno se nahlédne, že M akceptuje slovo u právě tehdy, když u náleží do jazyka
{w | abba.w ∈ L1}, tedy že {w | abba.w ∈ L1} = L(M ):
• u ∈ {w | abba.w ∈ L1} ⇒ abba.u ∈ L1 ⇒ M akceptuje abba.u ⇒ M akceptuje
u ⇒ u ∈ L(M ),
• u /∈ {w | abba.w ∈ L1} ⇒ abba.u /∈ L1 ⇒ M zamítá abba.u ⇒ M zamítá
u ⇒ u /∈ L(M ).
Doplnění slova abba před vstupní slovo u lze realizovat na úplném dvoupáskovém Turingově
stroji. Na první pásce máme vstup u, na druhou pásku napíšeme řetězec abba
a za něj zkopírujeme slovo u. Simulace stroje M na slově abba.u skončí v konečném
čase, neboť M je úplný. Výsledný stroj M je tedy také úplný.
Neboť jsme sestrojili úplný Turingův stroj M takový, že L(M ) = {w | abba.w ∈ L1},
je jazyk {w | abba.w ∈ L1} rekursivní.