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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (14 мая 2011)

В математике, логике и информатике рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый, или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE.

Существуют три основных эквивалентных определения концепции рекурсивно перечислимого языка.

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

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

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

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

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

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

Гладкий А. В. Формальные грамматики и языки. — М.: «Наука», 1973. — 368 с.