IB102 – úkol 9, příklad 1 – řešení Odevzdání: 7. 12. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Nechť Σ je libovolná 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) L1 je deterministický bezkontextový a L2 je regulární =⇒ co−L1∩L2 je bezkontextový
b) L1 je kontextový a L2 je bezkontextový =⇒ L1 ∪ L2 není bezkontextový
c) L1 je bezkontextový a L2 je rekurzivně spočetný =⇒ L2 \ L1 je rekurzivně spočetný
d) L1 není bezkontextový a L2 je regulární =⇒ L2 \ L1 není bezkontextový
a) Tvrzení platí. Platnost tohoto tvrzení plyne přímo z uzávěrových vlastností. Třída
DCFL je uzavřená na doplněk. Protože L1 je DCFL, tak i co−L1 je DCFL, a tedy
i CFL. Jazyk L2 je regulární a z uzavřenosti třídy CFL na průnik s regulárním jazykem
vyplývá, že co−L1 ∩ L2 je CFL.
b) Tvrzení neplatí, vyvrátíme jej protipříkladem. Všimneme si, že pokud za jeden z jazyků
zvolíme Σ∗
(je jedno, za který z nich, protože Σ∗
je kontextový i bezkontextový),
pak L1 ∪ L2 je jazyk Σ∗
.
c) Tvrzení platí. L2 \L1 si můžeme přepsat na L2 ∩(co−L1). Jazyk L1 je bezkontextový,
a tedy i rekurzivní. Rekurzivní jazyky jsou uzavřené na doplněk, proto i co−L1 je rekurzivní,
a tedy i rekurzivně spočetný. Jazyk L2 ∩(co−L1) je také rekurzivně spočetný,
protože rekurzivně spočetné jazyky jsou uzavřené na průnik.
d) Tvrzení neplatí. Jako protipříklad zvolíme L2 = ∅ a za L1 libovolný jazyk, který není
bezkontextový (například {an
bn
cn
| n ∈ N}). L2 \ L1 je potom rovno ∅ a jazyk ∅
bezkontextový je.