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

К:Википедия:Статьи без источников (тип: не указан)

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

Определения

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

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

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

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

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

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

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

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

Литература

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

Отрывок, характеризующий Рекурсивно перечислимый язык

Князь Андрей хотел тотчас же уехать, но княжна Марья упросила остаться еще день. В этот день князь Андрей не виделся с отцом, который не выходил и никого не пускал к себе, кроме m lle Bourienne и Тихона, и спрашивал несколько раз о том, уехал ли его сын. На другой день, перед отъездом, князь Андрей пошел на половину сына. Здоровый, по матери кудрявый мальчик сел ему на колени. Князь Андрей начал сказывать ему сказку о Синей Бороде, но, не досказав, задумался. Он думал не об этом хорошеньком мальчике сыне в то время, как он его держал на коленях, а думал о себе. Он с ужасом искал и не находил в себе ни раскаяния в том, что он раздражил отца, ни сожаления о том, что он (в ссоре в первый раз в жизни) уезжает от него. Главнее всего ему было то, что он искал и не находил той прежней нежности к сыну, которую он надеялся возбудить в себе, приласкав мальчика и посадив его к себе на колени.
– Ну, рассказывай же, – говорил сын. Князь Андрей, не отвечая ему, снял его с колон и пошел из комнаты.
Как только князь Андрей оставил свои ежедневные занятия, в особенности как только он вступил в прежние условия жизни, в которых он был еще тогда, когда он был счастлив, тоска жизни охватила его с прежней силой, и он спешил поскорее уйти от этих воспоминаний и найти поскорее какое нибудь дело.
– Ты решительно едешь, Andre? – сказала ему сестра.
– Слава богу, что могу ехать, – сказал князь Андрей, – очень жалею, что ты не можешь.
– Зачем ты это говоришь! – сказала княжна Марья. – Зачем ты это говоришь теперь, когда ты едешь на эту страшную войну и он так стар! M lle Bourienne говорила, что он спрашивал про тебя… – Как только она начала говорить об этом, губы ее задрожали и слезы закапали. Князь Андрей отвернулся от нее и стал ходить по комнате.
– Ах, боже мой! Боже мой! – сказал он. – И как подумаешь, что и кто – какое ничтожество может быть причиной несчастья людей! – сказал он со злобою, испугавшею княжну Марью.
Она поняла, что, говоря про людей, которых он называл ничтожеством, он разумел не только m lle Bourienne, делавшую его несчастие, но и того человека, который погубил его счастие.
– Andre, об одном я прошу, я умоляю тебя, – сказала она, дотрогиваясь до его локтя и сияющими сквозь слезы глазами глядя на него. – Я понимаю тебя (княжна Марья опустила глаза). Не думай, что горе сделали люди. Люди – орудие его. – Она взглянула немного повыше головы князя Андрея тем уверенным, привычным взглядом, с которым смотрят на знакомое место портрета. – Горе послано им, а не людьми. Люди – его орудия, они не виноваты. Ежели тебе кажется, что кто нибудь виноват перед тобой, забудь это и прости. Мы не имеем права наказывать. И ты поймешь счастье прощать.