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  (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 . 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.

 nie je uzavretá na
 komplement (pozri napr. diagonálny jazyk a univerzálny jazyk).

Kategória:Formálne jazyky
Kategória:Alan Turing