Aplicação correta do Lema de Bombeamento CFL

Question

Me deparei com esta pergunta sobre mostrar que a linguagem $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$é livre de contexto, mas não linear no livro de Peter Linz. Isso é facilmente realizável pelo lema do bombeamento separado para linguagens lineares (conforme apresentado no livro de Linz), mas minha pergunta é diferente.

Evidentemente, este é um CFL, e um autômato pushdown pode ser construído para ele. Mas se eu aplicar o lema do bombeamento para CFLs, descubro que sou capaz de bombear strings que não pertencem à linguagem, o que significaria que a linguagem não é um CFL. É claro que estou fazendo algo errado.

Usando o formato "semelhante a um jogo" fornecido em Linz, digamos que você escolha $w = a^mb^mc^{2m}$, $|w| \ge m$. O adversário pode escolher uma série de decomposições$w = uvxyz$, eles podem ser parecidos com -:

• $v = a^k, y = a^l$: O caso onde $|vxy|$ está contido no $a$da corda. Bomba$i = 0$, e depois $w_0 = a^{m – (k + l)}b^mc^{2m}$ não pode estar no idioma, pois a igualdade não é mais válida.
• $v = a^k, y = b^l$: O caso onde $v$ está no $a$ seção, $x$ abrange todo o $a$'areia $b$'areia $y$ está no $b$seção. Novamente, bomba$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ não pode estar no idioma.

Existem mais casos como este. Onde estou errando na aplicação do CFL PL?

Answer 1

O lema do bombeamento para CFL afirma que se $L$ é um CFL, existe uma constante $N \ge 1$ tal que para todos $\omega \in L$ com $\lvert \omega \rvert \ge N$ há uma divisão $\sigma = u v w x y$ com $\lvert v w x \rvert \le N$ e $v x \ne \varepsilon$ de tal modo que $u v^k w x^k y \in L$ para todos $k \ge 0$.

(O lema do bombeamento para linguagens regulares é semelhante, a discussão abaixo se aplica com pequenas alterações).

Você quer provar por contradição que $L$não é um CFL. Então você assume$L$é um CFL e obtém uma contradição com o lema. Isso significa, em detalhes:

• Como $L$é um CFL, ele satisfaz o lema. Em particular, há uma constante$N$ de tal modo que...
• Como o lema afirma todas as strings longas em$L$ pode ser dividido, você é livre para escolher um que seja fácil de trabalhar.
• O lema afirma que há alguma divisão de$\omega$tal que .... para todos $k \ge 0$...; para contradizer o lema, você precisa provar que nenhuma divisão funciona. Na prática, você pega uma determinada divisão de seu$\omega$( qualquer divisão) e para isso escolha alguns$k$para isso isso não dá um string na linguagem. Você pode precisar dividir isso em casos.

O que acontece com strings que não pertencem ao idioma ou são menores que $N$, é completamente irrelevante. Pode ser que algumas strings possam ser bombeadas, que alguns valores de$k$trabalhar para todas as cordas, ... O que é crucial é que para uma corda$\omega$(aquele que você escolheu) nenhuma divisão funciona com um valor de$k$(novamente, aquele que você escolheu). Como afirma o lema, ele funciona para todas as strings longas o suficiente, com alguma divisão para todas $k$, um contra-exemplo é suficiente. Exemplos infinitos não provam nada.