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 formalneEdytuj

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ściEdytuj

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żEdytuj

PrzypisyEdytuj

  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.