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

Question

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

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

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

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

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

Answer 1

L = {0^n 1^n: n natural} является нерегулярным контекстом бесплатно.

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

N = L∪M является нерегулярным контекстом бесплатно. N содержит M.

Answer 2

Для языка 0^n 1^n может оказаться полезным взглянуть на pumping lemma.. Я думаю, когда я узнал лемму о перекачке, она использовалась на языке 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

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

Answer 4

Поскольку вы просто хотите намеки (и, к счастью, так, так как я забыл, как сделать доказательства после колледжа), обратите внимание на definition of a regular language и какие свойства она обладает. Просто посмотрев, у меня было достаточно информации, чтобы доказать это утверждение.

Answer 5

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

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