Теория вычислений - Использование леммы прокачки для контекстно-свободных языков

Question

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

A = {0^n 1^m 0^n | n>=1, m>=1}  Prove that A is not regular.

Совершенно очевидно, что для этого нужно использовать лемму прокачки. Итак, у нас есть

1. | уу | > = 1
2. | Уха | <= p (p - накачка длина,> = 1)
3. uv ^ ixy ^ iz существует в A для всех i> = 0

Попытка придумать правильную строку для выбора кажется немного сомнительной для этого. Я думал 0 ^ p 1 ^ q 0 ^ p, но я не знаю, смогу ли я смутно сделать q, и, поскольку нет никаких ограничений на вас, это может сделать вещи неуправляемыми ..

Итак, как можно поступить об этом?

Answer 1

Будет намного проще, если вы будете использовать определение леммы прокачки, применяемое к обычным языкам, а не то, которое применяется к CFG. Три условия, которые должна иметь любая обычная строка s = xyz:

1. Для каждого i> = 0 xy ^ iz находится в A
2. | у | > = 0
3. | х | <= p </li>

Попробуйте использовать 0 ^ p1 ^ q0 ^ p еще раз, используя эти три условия.

Подсказка: поскольку у нас 0 ^ p, у будет состоять только из 0. Поэтому, когда мы «накачаем» больше y (рассмотрим xyyz), мы не получим строку на языке.

Answer 2

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

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

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

Answer 3

Я бы решил это без леммы: - Рассмотрим h (a), где h (1) = 1 h (2) = 0 h (0) = 0. Применение h ^ -1 на вашем языке, а затем пересечение с 0 ^ * 1 ^ 2 ^ дает вам язык 0 ^ n1 ^ m2 ^ n. - Теперь используйте h '(a), где h' (0) = a, h '(1) = эпсилон, h' (2) = b. Вы получаете ^ nb ^ n, который не является регулярным.

Почему это проще? Потому что, изучив эти основные приемы, вы легко сможете решить эти проблемы.

Что касается леммы: - Вам понадобится, чтобы любая подстрока слова в A при использовании в качестве подстроки испортила ваш язык. Я вижу 6 случаев (только 0 с начала, 0 с начала и 1 и т. Д.)

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