Рубрики

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

Рекурсивный перечислимый (RE) или язык типа -0

Языки RE или языки типа 0 генерируются грамматиками типа 0. Язык RE может быть принят или распознан машиной Тьюринга, что означает, что он войдет в конечное состояние для строк языка и может или не может перейти в состояние отклонения для строк, которые не являются частью языка. Это означает, что TM может зацикливаться на строки, которые не являются частью языка. Языки RE также называются узнаваемыми по Тьюрингу языками.

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

Рекурсивный язык (подмножество RE) может быть определен машиной Тьюринга, что означает, что он войдет в конечное состояние для строк языка и отклонит состояние для строк, которые не являются частью языка. например; L = {a n b n c n | n> = 1} является рекурсивным, потому что мы можем построить машину Тьюринга, которая переместится в конечное состояние, если строка имеет форму a n b n c n, иначе переместится в неконечное состояние , Таким образом, ТМ всегда остановится в этом случае. Языки REC также называются разрешимыми языками Тьюринга. Взаимосвязь между языками RE и REC может быть показана на рисунке 1.

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

  • Объединение : если L1 и L2 являются двумя рекурсивными языками, их объединение L1∪L2 также будет рекурсивным, поскольку, если TM останавливается для L1 и останавливается для L2, оно также останавливается для L1∪L2.
  • Конкатенация: если L1 и L2 — два рекурсивных языка, их конкатенация L1.L2 также будет рекурсивной. Например:
        L1= {anbncn|n>=0} 
        L2= {dmemfm|m>=0}
        L3= L1.L2
        = {anbncndm emfm|m>=0 and n>=0} is also recursive.
    

    L1 говорит п нет. из а следуют п нет. из б, сопровождаемых п нет. из с. L2 говорит, что нет. из D следует М нет. из E следует М нет. из ф. Их конкатенации первых совпадений нет. а, б и с, а затем соответствует нет. из д, е и ф. Так что это может решить ТМ.

  • Закрытие Клини: Если L1 является рекурсивным, его замыкание Клини L1 * также будет рекурсивным. Например:
         L1= {anbncn|n>=0}
         L1*= { anbncn||n>=0}* is also recursive.
  • Пересечение и дополнение : Если L1 и L2 — два рекурсивных языка, их пересечение L1 ∩ L2 также будет рекурсивным. Например:
        L1= {anbncndm|n>=0 and m>=0} 
        L2= {anbncndn|n>=0 and m>=0}
        L3=L1 ∩ L2
        = { anbncndn |n>=0} will be recursive.
    

    L1 говорит п нет. из а следуют п нет. из б, сопровождаемых п нет. с, а затем любой нет. из д. L2 говорит, что нет. из а следуют п нет. из б, сопровождаемых п нет. с с последующим п нет. из д. Их пересечение говорит, что нет. из а следуют п нет. из б, сопровождаемых п нет. с с последующим п нет. из д. Так что это можно решить с помощью машины Тьюринга, следовательно, рекурсивно.
    Точно так же дополнение рекурсивного языка L1, который является ∑ * -L1, также будет рекурсивным.

Примечание: В отличие от языков REC, языки RE не закрыты в дополнении, что означает, что дополнение языка RE не обязательно должно быть RE.

ВОРОТА Вопросы

Вопрос 1: Какое из следующих утверждений ЛОЖНО?
1. Для каждой недетерминированной ТМ существует эквивалентная детерминированная ТМ.
2. На узнаваемых языках закрыты при объединении и дополнении.
3. Турецкие разрешимые языки закрыты на пересечении и дополнении.
4. На узнаваемых языках закрыты под объединением и пересечением.

А.1 и 4
Б.1 и 3
С.2
Д.3

Решение:

Утверждение 1 верно, поскольку мы можем преобразовать каждую недетерминированную ТМ в детерминированную ТМ.
Утверждение 2 неверно, поскольку распознаваемые языки Тьюринга (языки RE) не закрываются при дополнении.
Утверждение 3 верно, поскольку разрешимые языки Тьюринга (языки REC) закрыты на пересечении и дополнении.
Утверждение 4 верно, так как распознаваемые языки Тьюринга (языки RE) закрыты на объединение и пересечение.

Вопрос 2: Пусть L — язык, а L — его дополнение. Что из перечисленного НЕ является жизнеспособной возможностью?
А. Ни L, ни L 'не являются RE.
B. Один из L и L 'является RE, но не рекурсивным; другой не RE.
C. Оба L и L 'RE, но не рекурсивные.
D. Оба L и L 'являются рекурсивными.

Решение:

Вариант A является правильным, потому что если L не RE, его дополнение не будет RE. Вариант B является правильным, потому что если L является RE, L 'не обязательно должно быть RE или наоборот, потому что языки RE не закрываются при дополнении.
Опция C ложна, потому что если L — RE, L 'не будет RE. Но если L является рекурсивным, L 'также будет рекурсивным, и оба будут также RE, потому что языки REC являются подмножеством RE. Как они уже упоминали, чтобы не быть REC, опция ложна.
Опция D верна, потому что если L рекурсивно, L 'также будет рекурсивно.

Вопрос 3: Пусть L1 — рекурсивный язык, и пусть L2 — рекурсивно перечислимый, но не рекурсивный язык. Что из следующего является ИСТИННЫМ?

A.L1 ′ рекурсивно, а L2 ′ рекурсивно перечислимо
B.L1 ′ рекурсивно, а L2 ′ не рекурсивно перечислимо
C.L1 ′ и L2 ′ рекурсивно перечислимы
D.L1 ′ рекурсивно перечислимо, а L2 ′ рекурсивно
Решение:

Опция A является False, поскольку L2 'не может быть рекурсивным перечислимым (L2 — RE, а RE не закрываются при дополнении).
Вариант B является правильным, поскольку L1 'является REC (языки REC закрыты при дополнении), а L2' не является рекурсивным перечислимым (языки RE не закрываются при дополнении).
Опция C является False, поскольку L2 'не может быть рекурсивным перечислимым (L2 — RE, а RE не закрываются при дополнении).
Опция D — False, поскольку L2 'не может быть рекурсивным перечислимым (L2 — RE, а языки RE не закрываются при дополнении). Поскольку языки REC являются подмножеством RE, L2 'также не может быть REC.

Эта статья предоставлена Sonal Tuteja . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes