Rekurzívne vyčísliteľný jazyk

Trieda rekurzívne vyčísliteľných jazykov je triedou jazykov generovaných frázovými gramatikami. Súčasne je to presne trieda jazykov rozpoznávaných Turingovými strojmi. Symbolicky ju označujeme ${\mathcal {L}}_{RE}$ (RE je značka z angl. recursively enumerable).

Frázové gramatiky (resp. Turingove stroje) sú veľmi silné a takmer každý "rozumný" predstaviteľný jazyk je rekurzívne vyčísliteľný. Je teda prirodzené sa pýtať, či naozaj každý jazyk sa dá generovať frázovou gramatikou. Pozrime sa na jazyky definované nad abecedou $\{0,1\}$. Jazykov nad touto abecedou je zrejme nespočítateľne veľa, kým všetky frázové gramatiky tvoria len spočítateľnú množinu. Tento jednoduchý argument nám dáva na našu otázku zápornú odpoveď. Príkladom jazyka, ktorý nie je rekurzívne vyčísliteľný, je komplement diagonálneho jazyka alebo komplement univerzálneho jazyka.

Názov tejto triedy je odvodený od rekurzívne vyčísliteľných množín.

Uzáverové vlastnosti

Trieda rekurzívne vyčísliteľných jazykov je uzavretá na

• zjednotenie,
• prienik,
• zreťazenie,
• Kleeneho uzáver (iteráciu),
• kladný uzáver
• reverz,
• homomorfizmus, inverzný homomorfizmus.

${\mathcal {L}}_{RE}$ nie je uzavretá na

• komplement (pozri napr. diagonálny jazyk a univerzálny jazyk).