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

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

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

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

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

Определения

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

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

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

Примеры

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

{displaystyle L = {, win {a, b, c} ^ {*} mid w = a ^ {n} b ^ {n} c ^ {n} {mbox {для некоторых}} ngeq 1,}}

является контекстно-зависимым и, следовательно, рекурсивным.

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

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

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

В Клини звезда ${displaystyle L ^ {*}}$
Образ φ (L) при е-свободный гомоморфизм φ
Конкатенация ${displaystyle Lcirc P}$
Союз ${displaystyle Lcup P}$
Перекресток ${displaystyle Lcap P}$
Дополнение ${displaystyle L}$
Установленная разница ${displaystyle L-P}$

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

Смотрите также

использованная литература

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