Uzávěrové vlastnosti rekurzivních a rek. spočetných jazyků
Řešení Příkladu 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í
Neplatí. Uvažujme jazyky
R = {a∗b∗c∗},
L = {anbncn | n ≥ 0}
splňující předpoklady tvrzení. Jejich průnik R ∩ L = L není zcela jistě regulární jazyk.
b) L je rekurzivní =⇒ co-L je rekurzivní
Platí na základě uzávěrových vlastností třídy rekurzivních jazyků.
c) L je rekurzivní =⇒ L∗ je rekurzivní
Platí na základě uzávěrových vlastností třídy rekurzivních jazyků.
d) L je kontextový =⇒ co-L je rekurzivní
Platí. Každý kontextový jazyk je zároveň také rekurzivní. Protože třída rekurzivních jazyků
je uzavřena na operaci doplněk, je i jazyk co-L rekurzivní.
e) L není rekurzivní =⇒ co-L není rekurzivní
Platí. Nechť L je nerekurzivní jazyk. Předpokládejme sporem, že jazyk K = co-L je rekurzivní.
Dle uzávěrových vlastností třídy rekurzivních jazyků je jazyk co-K = co-(co-L) = L
rekurzivní. To je spor s úvodním předpokladem. Zadané tvrzení tedy platí.
f) L není rekurzivní a R je rekurzivní =⇒ L \ R není rekurzivní
Neplatí. Ukážeme to pomocí následujícího protipříkladu. Buď L libovolný nerekurzivní jazyk
nad abecedou {a, b, c}∗. Dále nechť R = {a, b, c}∗. Jistě je R rekurzivní (každý regulární jazyk
patří též mezi rekurzivní jazyky). Jazyk L \ R = ∅ je regulární, tudíž i rekurzivní.
g) L není rekurzivní, R je rekurzivní a R ⊆ L =⇒ L \ R není rekurzivní
Platí. Jelikož R ⊂ L, platí vztah L = R ∪ (L \ R). Předpokládejme sporem, že L \ R je
rekurzivní. Dle předpokladů věty je i jazyk R rekurzivní, sjednocení L = R ∪ (L \ R) je tedy
rekurzivní jazyk dle uzávěrových vlastností. To je ovšem spor s předpokladem, že L není
rekurzivní. Původní tvrzení tedy platí.
1