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

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

Этот тип языка не определен в иерархии Хомского (Chomsky 1959).

Определения

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

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

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

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

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

• замыкание Клини <math>L^*</math>;
• образ <math>\varphi\left(L\right)</math>, где <math>\varphi</math> — гомоморфизм, такой что <math>\forall x ~ x\ne\varepsilon \Rightarrow \varphi\left(x\right) \ne \varepsilon</math>, где <math>\varepsilon</math> — пустая цепочка;
• конкатенация <math>L \circ P</math>;
• объединение <math>L \cup P</math>;
• пересечение <math>L \cap P</math>;
• дополнение <math>\overline L</math>;
• разность <math>L \setminus P</math>.

Список литературы

• Michael Sipser. Decidability // Introduction to the Theory of Computation. — PWS Publishing, 1997. — P. 151–170. — ISBN 0-534-94728-X.
• Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control 2 (2): 137–167. DOI:10.1016/S0019-9958(59)90362-6.

См. также

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

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

Ростов взял деньги, избегая взгляда Телянина, и, не говоря ни слова, пошел из комнаты. Но у двери он остановился и вернулся назад. – Боже мой, – сказал он со слезами на глазах, – как вы могли это сделать?
– Граф, – сказал Телянин, приближаясь к юнкеру.
– Не трогайте меня, – проговорил Ростов, отстраняясь. – Ежели вам нужда, возьмите эти деньги. – Он швырнул ему кошелек и выбежал из трактира.


Вечером того же дня на квартире Денисова шел оживленный разговор офицеров эскадрона.
– А я говорю вам, Ростов, что вам надо извиниться перед полковым командиром, – говорил, обращаясь к пунцово красному, взволнованному Ростову, высокий штаб ротмистр, с седеющими волосами, огромными усами и крупными чертами морщинистого лица.
Штаб ротмистр Кирстен был два раза разжалован в солдаты зa дела чести и два раза выслуживался.
– Я никому не позволю себе говорить, что я лгу! – вскрикнул Ростов. – Он сказал мне, что я лгу, а я сказал ему, что он лжет. Так с тем и останется. На дежурство может меня назначать хоть каждый день и под арест сажать, а извиняться меня никто не заставит, потому что ежели он, как полковой командир, считает недостойным себя дать мне удовлетворение, так…
– Да вы постойте, батюшка; вы послушайте меня, – перебил штаб ротмистр своим басистым голосом, спокойно разглаживая свои длинные усы. – Вы при других офицерах говорите полковому командиру, что офицер украл…
– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.