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^[1]. 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 ${\displaystyle 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 ${\displaystyle M_{L},}$ która dla każdego słowa ${\displaystyle x}$ zatrzyma się i da odpowiedzi:
   • Jeśli ${\displaystyle x\in L,}$ to ${\displaystyle M_{L}(x)=}$ tak
   • Jeśli ${\displaystyle x\not \in L,}$ to ${\displaystyle M_{L}(x)=}$ nie

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

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^[3].
2. Język ${\displaystyle L}$ jest językiem rekurencyjnym wtedy i tylko wtedy, gdy zarówno ${\displaystyle L,}$ jak i jego dopełnienie ${\displaystyle {\overline {L}}}$ są rekurencyjnie przeliczalne^[4].

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

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

Zobacz też

• funkcja rekurencyjna
• teoria rekursji

Przypisy

1. A.M Turing. On computable numbers, with an application to the Entscheidungsproblem. „Proceedings of the London Mathematical Society”. 2(42), s. 230–265, 1936.
2. Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 42. ISBN 978-83-204-3335-7.
3. Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 43. ISBN 978-83-204-3335-7.
4. Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 79. ISBN 978-83-204-3335-7.