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 nazywa się językiem rekurencyjnym, gdy:

  1. jest on podzbiorem rekurencyjnym zbioru wszystkich słów nad alfabetem tego języka.
  2. 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[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 jest językiem rekurencyjnym wtedy i tylko wtedy, gdy zarówno jak i jego dopełnienie są rekurencyjnie przeliczalne[4].

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

  1. Domknięcie Kleene’ego
  2. Homomorfizm bez przekształceń dla każdego
  3. Konkatenację
  4. Sumę teoriomnogościową
  5. Iloczyn teoriomnogościowy
  6. Dopełnienie [4]
  7. Różnicę

Zobacz też

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. a b Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 79. ISBN 978-83-204-3335-7.