1. Indique el lema de bombeo (¡con cuidado!)
Antes de comenzar, es esencial comprender la declaración de Lemma de bombeo *exactamente *. Aquí hay una formulación común:
Lema de bombeo para CFL:
Si L es un lenguaje libre de contexto, entonces existe un entero *p *(la "longitud de bombeo") de modo que para cualquier cadena *S *en L con longitud mayor o igual a *p *(| s | ≥ *p *), *S *se puede dividir en cinco subcandrices:*S =Uvxyz *, satisfaciendo las siguientes condiciones:
* | vxy | ≤ * p * (la porción media que se bombea no es demasiado larga)
* | Vy | ≥ 1 (la sección bombeada no está vacía)
* Para todos * i * ≥ 0, * uv
2. Suponga que el lenguaje * es * sin contexto
Comience asumiendo, en aras de la contradicción, que el lenguaje *l *que desea probar es *no *sin contexto *es *, de hecho, sin contexto. Esta es la suposición inicial de que eventualmente refutará.
3. Sea * p * la longitud de bombeo
Como ha asumido que * l * está libre de contexto, el lema de bombeo * debe * aplicarse. Esto significa que existe una longitud de bombeo * P * (de la cual no conoce el valor exacto). Es crucial recordar que el adversario (quién sabe el lenguaje *no *libre de contexto e intenta engañarlo) puede elegir *P *. Su objetivo es encontrar una cadena que * no importa qué valor de P * se elija, las condiciones del lema de bombeo conducen a una contradicción.
4. Elija una cadena*S*∈*L*tal que |*S*| ≥ *p *
Este es un paso crítico. Debe seleccionar cuidadosamente una cadena *S *que pertenezca al idioma *l *y tenga una longitud mayor o igual a *p *. La elección de * S * es crucial para que la prueba funcione. Piense en la estructura de las cuerdas en su idioma y cómo el bombeo podría afectar esa estructura. El objetivo es elegir una cuerda cuyas propiedades se violarán cuando 'V' e 'Y' se bombeen de una manera dictada por el lema de bombeo. Esta elección *a menudo *implica establecer algunas partes de la cadena en función del valor *P *.
*Piense en las propiedades que hacen que las cadenas en el idioma le pertenecen. Luego, elija una cadena de tal manera que cuando se bombee cualquier subtracción, al menos una de las limitaciones para la membresía del idioma.
5. Considere todas las descomposiciones posibles * S =UVXYZ * Satisfactorio | Vxy | ≤ * p * y | vy | ≥ 1
El lema de bombeo establece que*cualquier*cadena*S*con |*S*| ≥ * P * se puede dividir de esta manera. Entonces, * su adversario * puede elegir cómo * S * se divide en * uvxyz * (sujeto a las restricciones | vxy | ≤ * p * y | vy | ≥ 1). Sin embargo, puede considerar todas las divisiones posibles. Debe mostrar que *no importa cómo *el adversario elija *u *, *v *, *x *, *y *y *z *, puede bombear la cadena para obtener una contradicción.
A menudo, esto implica considerar diferentes *casos *basados en dónde *V *y *y *podría caer dentro de la cadena *S *. Para cada caso, analizará lo que sucede cuando bombee *V *y *y *.
6. Demuestre que para algunos *i *≥ 0, la cadena *uv
Este es el núcleo de la contradicción. Para cada caso considerado en el paso 5, debe demostrar que existe algunos *i *(generalmente *i *=0 o *i *=2, pero a veces se necesitan otros valores) de modo que la cadena resultante *uv
* Cómo mostrar * uv
* que muestra que la cadena ahora tiene un número desigual de símbolos que anteriormente eran iguales. Por ejemplo, si * L * requiere el mismo número de 'A y' B, usted muestra que el bombeo hace que el recuento sea desigual.
* mostrando que el orden de los símbolos ahora es incorrecto. Por ejemplo, si * L * requiere que todas las 'A vengan antes de todos' B, muestra que el bombeo puede poner una 'B' antes de un 'A'.
* que muestra que una relación matemática entre los recuentos ya no se mantiene. Por ejemplo, si * L * requiere que el número de 'A sea el doble del número de' B, muestra que el bombeo viola esta relación.
7. Concluir que * L * no es * sin contexto
Dado que ha demostrado que la suposición de que * L * es libre de contexto conduce a una contradicción (el lema de bombeo debe mantenerse, pero ha demostrado un caso en el que no es así), puede concluir que su suposición inicial era falsa. Por lo tanto, * L * no es un lenguaje libre de contexto.
Ejemplo:el lenguaje l ={a
n
Probemos que * l * ={a
1. Asumir * L * está libre de contexto.
2. Sea * p * la longitud de bombeo Garantizado por el lema de bombeo.
3. Elija una cadena *S *: Sea*s*=a
4. Considere todas las divisiones posibles * S =Uvxyz * tal que | vxy | ≤ * p * y | vy | ≥ 1: Necesitamos considerar dónde las subcadenas *V *y *y *pueden ubicarse dentro de *S *. La restricción crucial es que | vxy | ≤ *p *. Esto limita las posibilidades significativamente:
* Caso 1:* vxy * consiste solo en 'a. Entonces * v * =a
j
y * y * =a
k
* Caso 2:* vxy * consiste solo en 'B's. Entonces * V * =B
* Caso 3:* vxy * consiste solo en 'C's. Entonces * V * =C
* Caso 4:* vxy * consiste en 'A y' B's. Desde | vxy | ≤ *P *, no puede incluir 'C's porque todos los *p *' a y *p *'b deben preceder a cualquier' c. Desde | Vy | ≥ 1, al menos uno de * V * o * y * debe contener un carácter. Por lo tanto * v * =a
j
Si bombeamos (*i*=2), obtenemos la cadena A
* Caso 5:* Vxy * consiste en 'B y' C's. Esto es simétrico para el caso 4. Nuevamente, la bombeo dará como resultado una cadena que no está en el idioma.
5. Contradicción: En todos los casos posibles, hemos demostrado que existe un *i *tal que *uv
6. Conclusión: Por lo tanto, nuestra suposición inicial de que * L * está libre de contexto debe ser falsa. Por lo tanto, * l * ={a
Consejos clave para usar el lema de bombeo:
* Comprenda el lema precisamente: Conozca la declaración y las condiciones exactas.
* Elección de cadenas estratégicas: La elección de * S * es crucial. Elija una cadena que resalte la propiedad que desea romper el bombeo. A menudo, establecer partes de la cadena basadas en * P * es útil.
* Análisis de casos cuidadosos: Considere todas las ubicaciones posibles para *V *y *y *dentro de *S *, dadas las restricciones | Vxy | ≤ * p * y | vy | ≥ 1.
* Elija el derecho * i *:Experimente con *i *=0, *i *=2, u otros valores para encontrar el que demuestre más claramente la violación de *L *. A veces * i * =0 hará que algo desaparezca, y * i * =2 hará que algo se duplique.
* Sea claro y riguroso: Explique exactamente por qué la cadena bombeada ya no está en *L *. Consulte las propiedades definitorias del idioma.
El lema de bombeo puede ser difícil de dominar. Practique con diferentes idiomas para obtener experiencia en la elección de cadenas apropiadas y manejar el análisis de casos. Recuerde, el objetivo es encontrar una cadena donde * cualquier * posible aplicación del lema de bombeo conduce a una contradicción. ¡Buena suerte!