A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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).
Formálne jazyky, automaty a gramatiky | |||
---|---|---|---|
Chomského hierarchia |
Gramatika | Jazyk | 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. |
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk