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

Привет, Вы узнаете о том , что такое рекурсивный язык, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое рекурсивный язык , настоятельно рекомендую прочитать все из категории Компьютерная лингвистика.

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

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

Определения

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

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

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

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

Рекурсивные языки замкнуты по перечисленным ниже операциям. Об этом говорит сайт https://intellect.icu . Таким образом, если L и P являются рекурсивными языками, то следующие языки также рекурсивны:

• замыкание Клини ;
• образ , где — гомоморфизм, такой что , где — пустая цепочка;
• конкатенация ;
• объединение ;
• пересечение ;
• дополнение ;
• разность .

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