Język rekurencyjny

Definicja intuicyjna:
Język rekurencyjny to rodzaj języka formalnego, dla którego mając podane reguły jego składni, da się opracować automatyczny sposób sprawdzania, czy dane słowo jest zbudowane zgodnie z tymi regułami (tzn. należy do języka) czy nie.

Język rekurencyjny to klasa języków formalnych. 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

Istnieją dwie równoważne definicje języków rekurencyjnych. Język formalny L nazywamy 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