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

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

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

Определения

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

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

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

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

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

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

Заметим, что рекурсивно перечислимые языки не являются замкнутыми относительно разности или дополнения. Разность множеств L\P может быть, а может не быть рекурсивно перечислимой. Если L рекурсивно перечислим, то дополнение к L рекурсивно перечислимо если и только если L также рекурсивен.


Wikimedia Foundation. 2010.

Нужна помощь с курсовой?

Полезное


Смотреть что такое "Рекурсивно перечислимый язык" в других словарях:

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

  • Список статей по математической логике —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не ус …   Википедия

  • семантика логическая —         СЕМАНТИКА ЛОГИЧЕСКАЯ раздел логической науки, в котором изучают отношения выражений языка к обозначаемым объектам и выражаемому содержанию. Если семантика как раздел семиотики имеет дело с общими аспектами интерпретации любого типа… …   Энциклопедия эпистемологии и философии науки

  • ЛОГИЧЕСКАЯ СЕМАНТИКА — раздел металогики, в к ром изучаются интерпретации логических исчислений. Осн. понятия Л. с. можно разделить на 2 группы: (1) понятия, применение к рых к выражениям логич. исчисления существенно зависит от выбора интерпретации (см. также Модель)… …   Философская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»