Uzávěrové vlastnosti rekurzivních a rek. spočetných jazyků
Příklad 11.3 (Sbírka příkladů)
O každé z následujících implikací rozhodněte, zda je pravdivá.
a) R je regulární, L je rekurzivně spočetný =⇒ R ∩ L je regulární
b) L je rekurzivní =⇒ co-L je rekurzivní
c) L je rekurzivní =⇒ L∗ je rekurzivní
d) L je kontextový =⇒ co-L je rekurzivní
e) L není rekurzivní =⇒ co-L není rekurzivní
f) L není rekurzivní a R je rekurzivní =⇒ L \ R není rekurzivní
g) L není rekurzivní, R je rekurzivní a R ⊆ L =⇒ L \ R není rekurzivní
1