Język rekurencyjny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[1]. Klasa języków rekurencyjnych nie została uwzględniona w hierarchii Chomsky'ego.

Definicje[edytuj | edytuj kod]

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[2].

Właściwości[edytuj | edytuj kod]

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 L jest językiem rekurencyjnym wtedy i tylko wtedy, gdy zarówno L, jak i jego dopełnienie \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 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}[4]
  7. Różnicę L_{1} - L_{2}

Zobacz też[edytuj | edytuj kod]

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