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