Рекурсивный язык

редактировать

В математике, логика и информатика, формальный язык (набор конечных последовательностей символов, взятых из фиксированного алфавит ) называется рекурсивным, если это рекурсивное подмножество множества всех возможных конечных последовательностей по алфавиту языка. Эквивалентно, формальный язык является рекурсивным, если существует полная машина Тьюринга (машина Тьюринга, которая останавливается для каждого заданного ввода), которая при заданной конечной последовательности символов в качестве входных данных принимает это, если он принадлежит к языку, и отвергает его в противном случае. Рекурсивные языки также называются разрешимыми .

. Концепция разрешимости может быть распространена на другие модели вычислений. Например, можно говорить о языках, разрешимых на недетерминированной машине Тьюринга. Следовательно, всякий раз, когда возможна двусмысленность, используется синоним «рекурсивного языка» - язык, разрешаемый по Тьюрингу,, а не просто разрешимый.

Класс всех рекурсивных языков часто называется R, хотя это имя также используется для класса RP.

Этот тип языка не был определен в иерархии Хомского из ( Хомский 1959). Все рекурсивные языки также рекурсивно перечислимы. Все обычные, контекстно-свободные и контекстно-зависимые языки рекурсивны.

Содержание

1 Определения
2 Примеры
3 Свойства замыкания
4 См. Также
5 Ссылки

Определения

Есть два эквивалентных основных определения концепции рекурсивного языка:

Рекурсивный формальный язык - это рекурсивный подмножество в наборе всех возможных слов в алфавите языка .
Рекурсивный язык - это формальный язык, для которого существует машина Тьюринга, которая при представлении любой конечной входной строки останавливается и принимает, если строка находится на языке и в противном случае останавливается и отклоняется. Машина Тьюринга всегда останавливается: она известна как решающий элемент и, как говорят, решает рекурсивный язык.

Согласно второму определению, любая проблема принятия решения может быть доказана как разрешимая демонстрируя для него алгоритм , который завершается на всех входах. неразрешимая проблема - это неразрешимая проблема.

Примеры

Как отмечалось выше, каждый контекстно-зависимый язык является рекурсивным. Таким образом, простым примером рекурсивного языка является множество L = {abc, aabbcc, aaabbbccc,...}; более формально, множество

L = {w ∈ {a, b, c} ∗ ∣ w = anbncn для некоторого n ≥ 1} {\ displaystyle L = \ {\, w \ in \ {a, b, c \} ^ {*} \ mid w = a ^ {n} b ^ {n} c ^ {n} {\ t_dv {для некоторых}} n \ geq 1 \, \}}

L = \ {\, w \ in \ {a, b, c \} ^ {*} \ mid w = a ^ {n} b ^ {n} c ^ {n} {\ t_dv {для некоторых}} n \ geq 1 \, \}

контекстно-зависимый и поэтому рекурсивный.

Примеры разрешимых языков, которые не зависят от контекста, описать сложнее. Для одного из таких примеров требуется некоторое знакомство с математической логикой : Арифметика Пресбургера - это теория натуральных чисел первого порядка с добавлением (но без умножения). В то время как набор правильно сформированных формул в арифметике Пресбургера не зависит от контекста, каждая детерминированная машина Тьюринга, принимающая набор истинных утверждений в арифметике Пресбургера, имеет время выполнения в худшем случае не менее $2 2 cn {\ displaystyle 2 ^ {2 ^ {cn}}}$ $2 ^ {2 ^ {cn}}$ , для некоторой константы c>0 (Fischer Rabin 1974). Здесь n обозначает длину данной формулы. Поскольку любой контекстно-зависимый язык может быть принят линейным ограниченным автоматом, и такой автомат может быть смоделирован детерминированной машиной Тьюринга с временем работы в худшем случае не более $cn {\ displaystyle c ^ {n}}$ $c ^ n$ для некоторой константы c набор действительных формул в арифметике Пресбургера не зависит от контекста. С положительной стороны, известно, что существует детерминированная машина Тьюринга, работающая во времени, не более трехкратном экспоненциальном от n, которая определяет набор истинных формул в арифметике Пресбургера (Oppen 1978). Таким образом, это пример языка, который разрешим, но не зависит от контекста.

Свойства замыкания

Рекурсивные языки закрываются при следующих операциях. То есть, если L и P - два рекурсивных языка, то следующие языки также рекурсивны:

звезда Клини $L ∗ {\ displaystyle L ^ {*}}$ $L ^ {*}$
Изображение φ (L) при гомоморфизме без e φ
Конкатенация $L ∘ P {\ displaystyle L \ circ P}$ $L \ circ P$
Объединение $L ∪ P {\ displaystyle L \ чашка P}$ $L \ чашка P$
Пересечение $L ∩ P {\ displaystyle L \ cap P}$ $L \ cap P$
Дополнение $L {\ displaystyle L}$ $L$
Заданная разница $L - P { \ displaystyle LP}$ $LP$

Последнее свойство следует из того факта, что различие множеств может быть выражено в терминах пересечения и дополнения.

См. Также

Ссылки

Майкл Сипсер (1997). «Разрешимость». Введение в теорию вычислений. PWS Publishing. С. 151–170. ISBN 978-0-534-94728-6. CS1 maint: ref = harv (ссылка )
Хомский, Ноам (1959). «Об некоторых формальных свойствах грамматик». Информация и контроль. 2 (2): 137–167. doi : 10.1016 / S0019-9958 (59) 90362-6. CS1 maint: ref = harv (link )
Fischer, Michael J. ; Rabin, Michael O. (1974). «Суперэкспоненциальная сложность арифметики Пресбургера». Труды симпозиума SIAM-AMS по прикладной математике. 7 : 27–41. CS1 maint: ref = harv (ссылка )
Оппен, Дерек К. (1978). «Верхняя граница 2 сложности арифметики Пресбургера». J. Comput. Syst. Sci. 16 (3): 323–332. doi : 10.1016 / 0022-0000 (78) 90021-1.