IB102 – úkol 9, příklad 2 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.