Нерегулярный контекстно-свободный язык и бесконечные регулярные подъязыки

Question

У меня была работа в университете, которая в основном говорила:

"Демонстрирует, что нерегулярный язык L = {0 ^ n 1 ^ n: n натуральный} не имеет бесконечных регулярных подъязыков."

Я продемонстрировал это противоречием. Я в основном сказал, что есть язык S, который является подъязыком L и это обычный язык. Поскольку возможными регулярными выражениями для S являются 0 *, 1 *, (1 + 0) * и (0o1) *. Я проверяю каждую грамматику и показываю, что ни одна из них не является частью языка L.

Однако, как я мог доказать, что ЛЮБОЙ нерегулярный контекстно-свободный язык не может содержать никаких регулярных бесконечных подъязыков?

Я не хочу доказательство как таковое, я просто хочу, чтобы его указывали в правильном направлении.

Answer 1

L = {0 ^ n 1 ^ n: n натуральный} нерегулярный контекстно-свободный.

M = 2 * 3 * бесконечно регулярный.

N = L∪M нерегулярно не зависит от контекста. N содержит М.

Answer 2

Для языка 0 ^ n 1 ^ n было бы полезно взглянуть на лемму прокачки . Думаю, когда я выучил лемму прокачки, она использовалась на языке a ^ nb ^ n ( То же самое.) Возможно, лемма прокачки может помочь в вашем доказательстве.

Также вы можете считать, что обычные языки закрыты под дополнением, объединением, пересечением и звездой клини.

То есть, если L1 и L2 регулярные, то:

L1 L2 (concatenation) is also regular.
L1 n L2 is regular
L1 U L2 is regular
¬L1 is regular 
L1* is regular

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

Answer 3

Ваши инстинкты хороши. Здесь две вещи.

Во-первых, почти всегда, когда вопрос принимает форму «покажите, что L не является регулярным / не CF», ответ будет включать использование лемм прокачки. Точно так же, когда вы получаете вопрос типа «покажите, что Х нет ...», легкий путь (почти всегда) будет доказательством от противного.

Answer 4

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

Answer 5

EDIT: ложное утверждение, применяется только к контекстно-свободному языку