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

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

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

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

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

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

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

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

• Michael Sipser^[англ.]. Decidability // Introduction to the Theory of Computation (англ.). — PWS Publishing, 1997. — P. 151—170. — ISBN 0-534-94728-X.
• Chomsky, Noam. On certain formal properties of grammars (англ.) // Information and Control^[англ.] : journal. — 1959. — Vol. 2, no. 2. — P. 137—167. — doi:10.1016/S0019-9958(59)90362-6.

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