Насосная лемма для КЛЛ

Question

Q: Покажите, что L = {ww | w ∈ {0,1} *} не является контекстно-свободным

Мое решение:

Предположим, что L не зависит от контекста

Пусть его длина накачки будет P

Таким образом,

строка = 0 ^ P 1 ^ P 0 ^ P 1 ^ P

пусть P = 2, S = 00 11 00 11

S можно разделить на u v ^ i x y ^ i z

0 0 110 0 11
u v  x  y  z

после прокачки,

0 00 110 00 11
u  v  x   y  z

0 ^ 3 1 ^ 2 0 ^ 3 1 ^ 2 поэтому он принимает форму ww (первое условие выполнено)

| уу | = 4> 0 (второе условие выполнено)

| vxy | = 7, что больше длины накачки 2 (3-е условие не выполнено)

Следовательно, противоречит предположению, что L не зависит от контекста.

Таким образом, L не является контекстно-свободным

---

Правильно ли мое доказательство?

Answer 1

Это доказательство неверно. Где это идет от рельсов здесь:

пусть P = 2, S = 00 11 00 11

Вы не можете "позволить" P быть чем-либо. Предполагается, что P существует из-за леммы прокачки для контекстно-свободных языков, но это пока еще гипотетическое число. Даже если остальные доказательства верны, все, что вы будете доказывать, это то, что число P = 2 не работает. Вам нужно доказать, что для P нет выбора, чтобы показать, что язык не является контекстно-свободным.

Следующая ошибка такова:

S можно разделить на u v ^ i x y ^ i z […]

Это правда, что S можно разделить, как вы предлагаете. Однако его можно разделить и на другие пути. Обратите внимание, что лемма прокачки для контекстно-свободных языков требует только | vxy |

0. В частности, любая из u, v, x, y и z может быть пустой строкой, если только v и y не пусты.

Вы определенно были на правильном пути с этим:

строка = 0 ^ P 1 ^ P 0 ^ P 1 ^ P

Отсюда, вместо того, чтобы выбирать конкретный P или конкретное назначение, рассмотрите интересные виды назначений или случаи в целом; количество интересных случаев на самом деле довольно мало.

1. v и y состоят только из 0 из первого раздела строки. Насос приводит к тому, что число 0 в первой части не соответствует следующим трем частям.
2. v и y состоят только из 0 и 1 из первого и второго разделов строки. Насос приводит к тому, что число нулей и / или единиц первого и второго участков струн не совпадает с третьим и четвертым участками.
3. v и y состоят только из 1 с из второго раздела строки. В основном так же, как (1)
4. v и y состоят из 1 и 0 из второго и третьего разделов строки. В основном так же, как (2)
5. v и y состоят из 0 из третьего раздела строки. В основном так же, как (1) и (3)
6. v и y состоят из 0 и 1 из третьего и четвертого разделов строки. В основном так же, как (2) и (4)
7. v и y состоят из 1 с четвертого раздела строки. В основном так же, как (1), (3) и (5).

Эти случаи охватывают все возможные назначения v и y, и ни один из них не может быть закачан, как гласит лемма. Это противоречие. Ключ использует | vxy |