Правильное применение леммы CFL о накачке

Aug 16 2020

Я столкнулся с этим вопросом о том, чтобы показать, что язык $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$не зависит от контекста, но не линейно в книге Питера Линца. Это легко сделать с помощью отдельной леммы о накачке для линейных языков (как указано в книге Линца), но мой вопрос в другом.

Очевидно, это КЛЛ, и для него можно сконструировать выталкивающий автомат. Но если я применяю лемму о перекачке для CFL, я обнаруживаю, что могу перекачивать строки, которые не принадлежат языку, что означало бы, что язык не является CFL. Явно что-то не так делаю.

Исходя из «игрового» формата, данного в Линце, скажем, вы выбираете $w = a^mb^mc^{2m}$, $|w| \ge m$. Противник может выбрать несколько разложений$w = uvxyz$, они могут выглядеть так -:

  • $v = a^k, y = a^l$: Случай, когда $|vxy|$ содержится в $a$строки. Насос$i = 0$, а потом $w_0 = a^{m – (k + l)}b^mc^{2m}$ не может быть на языке, поскольку равенство больше не выполняется.
  • $v = a^k, y = b^l$: Случай, когда $v$ находится в $a$ раздел, $x$ простирается через $a$и $b$s, и $y$ находится в $b$раздел. Опять качаем$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ не может быть на языке.

Таких случаев больше. Где я ошибаюсь в применении CFL PL?

Ответы

1 vonbrand Aug 17 2020 at 08:20

Лемма о накачке для CFL утверждает, что если $L$ является КЛЛ, существует постоянная $N \ge 1$ такой, что для всех $\omega \in L$ с участием $\lvert \omega \rvert \ge N$ есть разделение $\sigma = u v w x y$ с участием $\lvert v w x \rvert \le N$ и $v x \ne \varepsilon$ такой, что $u v^k w x^k y \in L$ для всех $k \ge 0$.

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

Вы хотите доказать от противного, что $L$не КЛЛ. Итак, вы предполагаете$L$является КФЛ, и получаем противоречие с леммой. В деталях это означает:

  • В виде $L$является КЛМ, для него выполняется лемма. В частности, существует постоянная$N$ такой, что ...
  • Как утверждает лемма, все длинные строки в$L$ можно разделить, вы можете выбрать тот, с которым легко работать.
  • Лемма утверждает, что существует некоторое разделение$\omega$такое, что .... для всех $k \ge 0$...; чтобы противоречить лемме, вам нужно доказать, что деление не работает. На практике вы берете определенную часть своего$\omega$( любое деление) и для него выберите несколько$k$для этого, который не дает строки на языке. Возможно, вам придется разделить это на случаи.

Что происходит со строками, которые не принадлежат языку или короче, чем $N$, совершенно не имеет значения. Может случиться так, что некоторые строки могут быть перекачаны, что некоторые значения$k$работать для всех строк, ... Важно то, что для одной строки$\omega$(тот, который вы выбрали) ни одно деление не работает с одним значением$k$(снова тот, который вы выбрали). Как утверждает лемма, она работает для всех достаточно длинных строк с некоторым делением для всех $k$, достаточно одного контрпримера. Бесконечные примеры ничего не доказывают.