Język rekurencyjny – rodzaj języka formalnego, dla którego z podanymi regułami jego składni da się opracować automatyczny sposób sprawdzania, czy dane słowo jest zbudowane zgodnie z tymi regułami (tzn. czy należy do języka).
W teorii złożoności oznaczana jest literą R. Klasa języków rekurencyjnych nie została uwzględniona w hierarchii Chomskiego.
Definicje formalne Istnieją dwie równoważne definicje języków rekurencyjnych. Język formalny nazywa się językiem rekurencyjnym, gdy: jest on podzbiorem rekurencyjnym zbioru wszystkich słów nad alfabetem tego języka. istnieje maszyna Turinga która dla każdego słowa zatrzyma się i da odpowiedzi: Jeśli to tak Jeśli to nie
Innymi słowy, język nazywamy rekurencyjnym, jeżeli istnieje dla niego maszyna Turinga jednoznacznie rozstrzygająca, czy słowo należy do języka czy nie.
Właściwości Ogólne właściwości języków rekurencyjnych:
Każdy język rekurencyjny jest językiem rekurencyjnie przeliczalnym. Język jest językiem rekurencyjnym wtedy i tylko wtedy, gdy zarówno jak i jego dopełnienie są rekurencyjnie przeliczalne.
Języki rekurencyjne są zamknięte ze względu na następujące operacje:
Domknięcie Kleene’ego Homomorfizm bez przekształceń dla każdego Konkatenację Sumę teoriomnogościową Iloczyn teoriomnogościowy Dopełnienie Różnicę
Zobacz też funkcja rekurencyjna teoria rekursji
Przypisy
Kategoria:Języki formalne