Uzávěrové vlastnosti jazyků TS

• Třídy rekurzivních a rekurzivně spočetných jazyků jsou uzavřeny vzhledem k operacím $\cup ,\cap ,\cdot {,}^{\ast }$.

Důkaz

• Poslední elementární operací nad jazyky je komplement (doplněk). Vzhledem k této operaci se třídy rekurzivních a rekurzivně spočetných jazyků chovají rozdílně. Zatímco komplement rekurzivního jazyka je vždy rekurzivní jazyk, komplement rekurzivně spočetného jazyka nemusí být rekurzivně spočetný.

Navigace

Předchozí: Vztah rekurzivních a částečně rekurzivních jazyků Následující: Riceova věta Celý okruh: 1. Teoretické základy informatiky