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

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

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.

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