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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

Содержание

Определения

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

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

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

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

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

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

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

  • Decidability // Introduction to the Theory of Computation. — PWS Publishing, 1997. — P. 151–170. — ISBN 0-534-94728-X
  • Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control 2 (2): 137–167. DOI:10.1016/S0019-9958(59)90362-6.

См. также

bs:Rekurzivni jezik

cs:Rekurzivní jazyk de:Rekursive Sprache en:Recursive language es:Lenguaje recursivo fr:Langage récursif hr:Rekurzivni jezik it:Linguaggio ricorsivo ja:帰納言語 pl:Język rekurencyjny pt:Linguagem recursiva sr:Рекурзивни језик zh:递归语言

Личные инструменты

Served in 0.118 secs.