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 Chomskiego.
Definicje formalne
[edytuj | edytuj kod]Istnieją dwie równoważne definicje języków rekurencyjnych. Język formalny nazywa się językiem rekurencyjnym, gdy:
- jest on podzbiorem rekurencyjnym zbioru wszystkich słów nad alfabetem tego języka.
- 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
[edytuj | edytuj kod]Ogólne właściwości języków rekurencyjnych:
- Każdy język rekurencyjny jest językiem rekurencyjnie przeliczalnym[3].
- 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:
- Domknięcie Kleene’ego
- Homomorfizm bez przekształceń dla każdego
- Konkatenację
- Sumę teoriomnogościową
- Iloczyn teoriomnogościowy
- Dopełnienie [4]
- Różnicę
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ A.M Turing. On computable numbers, with an application to the Entscheidungsproblem. „Proceedings of the London Mathematical Society”. 2(42), s. 230–265, 1936.
- ↑ Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 42. ISBN 978-83-204-3335-7.
- ↑ Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 43. ISBN 978-83-204-3335-7.
- ↑ a b Christos H. Papadimitrou: Złożoność obliczeniowa. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 79. ISBN 978-83-204-3335-7.