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 Chomskiego.

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\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 $\bar{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 $\varphi (L)$ bez przekształceń $\varphi (x)=ϵ$ dla każdego $x=ϵ$
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 $\bar{L}$
7. Różnicę $L_1-L_2$

Zobacz też

• funkcja rekurencyjna
• teoria rekursji