Język rekurencyjny

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 Chomsky’ego.

Definicje formalne

Istnieją dwie równoważne definicje języków rekurencyjnych. Język formalny $L$ nazywa się językiem rekurencyjnym, gdy:

1. jest on podzbiorem rekurencyjnym zbioru wszystkich słów nad alfabetem tego języka.
2. istnieje maszyna Turinga $M_{L},$ która dla każdego słowa $x$ zatrzyma się i da odpowiedzi:
   • Jeśli $x\in L,$ to $M_{L}(x)=$ tak
   • Jeśli $x\not \in L,$ to $M_{L}(x)=$ nie

Innymi słowy, język nazywamy rekurencyjnym, jeżeli istnieje dla niego maszyna Turinga jednoznacznie rozstrzygająca, czy słowo $x$ należy do języka czy nie.

Właściwości

Ogólne właściwości języków rekurencyjnych:

1. Każdy język rekurencyjny jest językiem rekurencyjnie przeliczalnym.
2. Język $L$ jest językiem rekurencyjnym wtedy i tylko wtedy, gdy zarówno $L,$ jak i jego dopełnienie ${\overline {L}}$ są rekurencyjnie przeliczalne.

Języki rekurencyjne są zamknięte ze względu na następujące operacje:

1. Domknięcie Kleene’ego $L^{*}$
2. Homomorfizm $\phi (L)$ bez przekształceń $\phi (x)=\epsilon$ dla każdego $x\not =\epsilon$
3. Konkatenację $L_{1}L_{2}$
4. Sumę teoriomnogościową $L_{1}\cup L_{2}$
5. Iloczyn teoriomnogościowy $L_{1}\cap L_{2}$
6. Dopełnienie ${\overline {L}}$
7. Różnicę $L_{1}-L_{2}$

Zobacz też

• funkcja rekurencyjna
• teoria rekursji