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

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

Рекурсивно перечислимые языки известны как языки типа 0 в Хомского иерархии формальных языков . Все обычные , контекстно-свободные , контекстно-зависимые и рекурсивные языки являются рекурсивно перечислимыми.

Класс всех рекурсивно перечислимых языков называется RE .

Определения

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

Рекурсивно перечислимый язык — это рекурсивно перечисляемое подмножество множества слов всех возможных алфавите языка в .
Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция ), которая будет перечислять все допустимые строки языка. Обратите внимание, что если язык бесконечен , предоставленный алгоритм перечисления может быть выбран так, чтобы избежать повторений, поскольку мы можем проверить, «уже» ли строка, созданная для числа n, создана для числа, которое меньше n . Если он уже создан, используйте вместо этого вывод для ввода n +1 (рекурсивно), но снова проверьте, является ли он «новым».
Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая останавливается и принимает любую строку на языке в качестве входных данных, но может либо останавливаться и отклонять, либо зацикливаться навсегда, когда ей представлена строка. не в языке. Сравните это с рекурсивными языками , которые требуют, чтобы машина Тьюринга останавливалась во всех случаях.

Все обычные , контекстно-свободные , контекстно-зависимые и рекурсивные языки являются рекурсивно перечислимыми.

Теорема Поста показывает, что RE вместе с его дополнением co-RE соответствуют первому уровню арифметической иерархии .

Пример

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

Некоторые другие рекурсивно перечислимые языки, которые не являются рекурсивными, включают:

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

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

звезда Клини $L^{*}$ Л
конкатенация $L\circ P$ L и P
союз $L\cup P$
пересечение $L\cap P$ .

Рекурсивно перечислимые языки не замкнуты относительно множества различий или дополнений. Разница в наборе $L-P$ является рекурсивно перечислимым, если $P$ является рекурсивным. Если $L$ рекурсивно перечислимо, то дополнение $L$ рекурсивно перечислим тогда и только тогда, когда $L$ также является рекурсивным.

См. также

Источники

Сипсер, М. (1996), Введение в теорию вычислений , PWS Publishing Co.
Козен, округ Колумбия (1997), Автоматы и вычислимость , Springer .

Внешние ссылки