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

Эта статья о классе формальных языков, изучаемых в математике и теоретической информатике. Информацию о компьютерных языках, которые позволяют функции рекурсивно вызывать себя, см. в разделе Рекурсия (информатика) .

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

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

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

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

Определения

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

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

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

Примеры

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

$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$

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

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

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

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

• Звезда Клини $L^{*}$
• Образ φ(L) при e-свободном гомоморфизме φ
• Конкатенация $L\circ P$
• Союз $L\cup P$
• Пересечение $L\cap P$
• Дополнение $L$
• Разница в наборе $L-P$

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

См. также

• Рекурсивно перечислимый язык
• Вычислимое множество
• Рекурсия

Ссылки

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