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

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

Определения

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

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

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

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

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

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

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

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

Литература

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