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

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

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

В математике, логике и информатике, рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE.

Определения

Существуют три основных эквивалентных определения концепции рекурсивно перечислимого языка.

  1. Рекурсивно перечислимый формальный язык, это рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка.
  2. Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая перечисляет все корректные строки языка. Заметим, что если язык бесконечен, то можно выбрать алгоритм перечисления, который избегает повторений, так как для строки под номером n можно проверить, была ли она "уже" выдана под номером меньшим n. Если была, то вместо этого использовать вывод под номером n+1 (рекурсивно), снова проверив, является ли он "новым".
  3. Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая остановится и примет любую входную строку из языка, но остановится и отвергнет или не остановится вообще для любой входной строки не из языка. Рекурсивные языки требуют останова машины Тьюринга в любом случае.

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

Теорема Поста показывает, что RE вместе с дополнительным co-RE соответствуют первому уровню арифметической иерархии.

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

Рекурсивно перечислимые языки являются замкнутыми относительно следующих операций. Пусть L и P — два рекурсивно перечислимых языка, тогда следующие языки также рекурсивно перечислимы:

Заметим, что рекурсивно перечислимые языки не являются замкнутыми относительно разности или дополнения. Разность множеств L\P может быть, а может не быть рекурсивно перечислимой. Если L рекурсивно перечислим, то дополнение к L рекурсивно перечислимо если и только если L также рекурсивен.cs:Rekurzivně spočetný jazyk de:Rekursiv aufzählbare Sprache en:Recursively enumerable language es:Lenguaje recursivamente enumerable hr:Rekurzivno prebrojiv jezik it:Linguaggio ricorsivamente enumerabile ja:帰納的可算言語 ko:재귀 열거 언어 pl:Język rekurencyjnie przeliczalny pt:Linguagem recursivamente enumerável sh:Rekurzivno prebrojiv jezik sk:Rekurzívne vyčísliteľný jazyk sr:Рекурзивно пребројив језик zh:递归可枚举语言

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

Served in 0.050 secs.