Если L и L-дополнение рекурсивно перечислимы, то почему L не может быть регулярным языком?

Ниже вопрос был задан в документе GATE 2008:

Если L и L' (дополнение L) рекурсивно перечислимы, то L равно ?

a) Обычный
b) CFL
c) CSL
d) Рекурсивный

Правильным вариантом был вариант (d), и я согласен с тем, что это правда. Но мой вопрос: почему это не может быть обычным или CSL?

Потому что я думаю, что если мы считаем, что L является регулярным, то L' также является регулярным (поскольку регулярные языки закрыты при дополнении). И теперь, поскольку L' является регулярным, то согласно "иерархии Хомского" L' также является рекурсивно перечислимым. Поскольку даже L после того, как он стал регулярным, он соответствует постановке вопроса, то почему вариант (а) не является правильным? То же самое касается CSL, так почему вариант (с) также не является правильным вариантом?


regular-language computation-theory enumerable chomsky-hierarchy
person Avi    schedule 30.09.2020    source источник
comment
Это может быть, но это не гарантируется.   -  person Chris Dodd    schedule 30.09.2020
comment
Но тогда как он может гарантированно быть рекурсивным?   -  person Avi    schedule 30.09.2020
comment
В постановке задачи говорится, что оно рекурсивно перечислимо и что L' рекурсивно перечислимо. Следовательно, L рекурсивен.   -  person Chris Dodd    schedule 30.09.2020
comment
Да ты прав. Но если в постановке задачи говорится, что L рекурсивно перечислим, это не значит, что он не может быть регулярным (потому что каждый обычный также рекурсивно перечислим). И теперь, если он регулярен, то L' регулярен, и теперь L' также можно назвать рекурсивным. Я имею в виду, что это возможный случай. Правильно?   -  person Avi    schedule 30.09.2020
comment
Он не говорит, что он нерегулярный (а может быть, поскольку все обычные языки рекурсивно перечислимы), но не говорит, что он регулярный. Таким образом, вы должны рассматривать ВСЕ рекурсивно перечисляемые языки, а не только обычные языки.   -  person Chris Dodd    schedule 30.09.2020

Ответы (2)


arrow_upward
0
arrow_downward

Краткий обзор языковых классов — мы знаем, что все эти 5 языковых классов являются (строгими) подмножествами друг друга:

регулярный ⊂ CFL ⊂ CSL ⊂ рекурсивный ⊂ рекурсивно перечислимый

Вопрос заключается в следующем: если мы знаем, что язык L рекурсивно перечислим И мы знаем, что его дополнение L' также рекурсивно перечислимо, что мы можем сказать наверняка, в каком меньшем классе L находится?

Ответ эквивалентен тому, что если язык L является рекурсивно перечислимым и НЕ рекурсивным, то L' НЕ является рекурсивно перечислимым. Это утверждение верно, но эквивалентное утверждение для любого из других языковых классов — нет.

person Chris Dodd    schedule 30.09.2020

arrow_upward
0
arrow_downward

Если L и L' оба рекурсивно перечислимы, то

а) L может быть регулярным (действительно, если L регулярен, то L' также регулярен, и все регулярные языки рекурсивно перечислимы)... но есть нерегулярные языки, дополнения которых рекурсивно перечислимы

b) L может быть CFL (существуют CFL, чьи дополнения также являются CFL, а также CFL, чьи дополнения не являются CFL)... но есть неконтекстно-свободные языки, дополнения которых рекурсивно перечислимы.

c) L может быть CSL (существуют CSL, чьи дополнения являются CSL)... но есть не зависящие от контекста языки, дополнения которых рекурсивно перечислимы

г) язык L должен быть рекурсивным, поскольку в силу того, что и L, и L' рекурсивно перечислимы, у нас есть эффективно вычислимая процедура для определения того, принадлежит ли какая-либо заданная строка языку L: начните перечислять строки в каждом языке, чередуя перечисления (таким образом, вы даете следующую строку в L, затем следующую строку в L', затем обратно в L и т. д.). Продолжая этот процесс, в конечном итоге целевая строка будет найдена либо в L, либо в L', и в этот момент вы можете вернуть true (если она была пронумерована в L) или false (если пронумерована в L').

Таким образом, хотя верно то, что L может быть обычным, CFL или CSL, также верно и то, что он может не быть ни одним из них; но он должен быть абсолютно рекурсивным. Следовательно, это лучший ответ и единственный, который вообще правильный во всех случаях.

person Patrick87    schedule 13.11.2020