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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определения[править | править исходный текст]

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

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

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

Свойства замкнутости[править | править исходный текст]

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

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

Список литературы[править | править исходный текст]

См. также[править | править исходный текст]