Aplicación correcta del lema de bombeo CFL
Me encontré con esta pregunta sobre mostrar que el idioma $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$es libre de contexto pero no lineal en el libro de Peter Linz. Eso es fácilmente factible mediante el lema de bombeo separado para lenguajes lineales (como se indica en el libro de Linz), pero mi pregunta es diferente.
Evidentemente se trata de una CFL, y se puede construir un autómata de empuje para ello. Pero si aplico el lema de bombeo para las CFL, encuentro que puedo bombear cadenas que no pertenecen al idioma, lo que significaría que el idioma no es un CFL. Claramente estoy haciendo algo mal.
Siguiendo el formato "similar a un juego" que se da en Linz, digamos que eliges $w = a^mb^mc^{2m}$, $|w| \ge m$. El adversario puede elegir una serie de descomposiciones$w = uvxyz$, pueden verse como -:
- $v = a^k, y = a^l$: El caso donde $|vxy|$ está contenido en el $a$de la cadena. Bomba$i = 0$, y entonces $w_0 = a^{m – (k + l)}b^mc^{2m}$ no puede estar en el idioma porque la igualdad ya no es válida.
- $v = a^k, y = b^l$: El caso donde $v$ está en el $a$ sección, $x$ se extiende a través del $a$y $b$y $y$ está en el $b$sección. De nuevo, bombea$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ no puede estar en el idioma.
Hay más casos como estos. ¿Dónde me equivoco en la aplicación de la CFL PL?
Respuestas
El lema de bombeo para CFL establece que si $L$ es una CFL, existe una constante $N \ge 1$ tal que para todos $\omega \in L$ con $\lvert \omega \rvert \ge N$ hay una división $\sigma = u v w x y$ con $\lvert v w x \rvert \le N$ y $v x \ne \varepsilon$ tal que $u v^k w x^k y \in L$ para todos $k \ge 0$.
(El lema de bombeo para idiomas regulares es similar, la discusión a continuación se aplica con cambios menores).
Quieres probar por contradicción que $L$no es una CFL. Entonces asumes$L$es una CFL y contradice el lema. Esto significa, en detalle:
- Como $L$es una CFL, satisface el lema. En particular, hay una constante$N$ tal que ...
- Como dice el lema, todas las cadenas largas en$L$ puede dividirse, puede elegir uno con el que sea fácil trabajar.
- El lema establece que hay alguna división de$\omega$tal que .... para todos $k \ge 0$...; para contradecir el lema hay que demostrar que la división no funciona. En la práctica, toma una división determinada de su$\omega$( cualquier división) y para ello elige algunos$k$por eso eso no da una cadena en el idioma. Es posible que deba dividir esto en casos.
¿Qué sucede con las cadenas que no pertenecen al idioma o son más cortas que $N$, es completamente irrelevante. Puede ser que se puedan bombear algunas cadenas, que algunos valores de$k$funcionan para todas las cadenas, ... Lo que es crucial es que para una cadena$\omega$(el que eligió) ninguna división funciona con un valor de$k$(de nuevo, el que elegiste). Como afirma el lema, funciona para todas las cadenas lo suficientemente largas, con alguna división para todas $k$, un contraejemplo es suficiente. Infinitos ejemplos no prueban nada.