Rekurzívne vyčísliteľný jazyk

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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

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

Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.