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

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

Определения

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

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}$ .

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

• (англ.) ( . Decidability // (англ.) . — PWS Publishing, 1997. — P. —170. — ISBN 0-534-94728-X .
• Chomsky, Noam. On certain formal properties of grammars (англ.) // (англ.) ( : journal. — 1959. — Vol. 2 , no. 2 . — P. 137—167 . — doi : .

См. также

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