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

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

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

Определения

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

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

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

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

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

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

См. также

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