Lema de bombeo para lenguajes libres de contexto

En ciencias de la computación , en particular en la teoría del lenguaje formal , el lema de bombeo para lenguajes libres de contexto , también conocido como el lema de Bar-Hillel , ^[1] es un lema que otorga una propiedad compartida por todos los lenguajes libres de contexto y generaliza el lema de bombeo . Lema para lenguajes regulares .

El lema de bombeo se puede utilizar para construir una prueba por contradicción de que un lenguaje específico no está libre de contexto. Por el contrario, el lema de bombeo no es suficiente para garantizar que un idioma esté libre de contexto; hay otras condiciones necesarias, como el lema de Ogden , o el lema de Intercambio .

Si un idioma no tiene contexto, entonces existe algún número entero (llamado " longitud de bombeo") ^[2] tal que cada cadena que tiene una longitud de o más símbolos (es decir, con ) puede escribirse como${\ estilo de visualización L}$${\ estilo de visualización p \ geq 1}$${\ estilo de visualización}$${\ estilo de visualización L}$${\ estilo de visualización p}$${\ estilo de visualización | s | \ geq p}$

con subcadenas y , tal que${\ estilo de visualización u, v, w, x}$${\ estilo de visualización y}$

Idea de prueba: si es lo suficientemente largo, su árbol de derivación con una gramática de forma normal de Chomsky debe contener algunos no terminales dos veces en algún camino del árbol (imagen superior). Repitiendo veces la parte de derivación ⇒...⇒ obtiene una derivación para (imagen inferior izquierda y derecha para y , respectivamente).${\ estilo de visualización}$ ${\ estilo de visualización N}$${\ estilo de visualización n}$${\ estilo de visualización N}$${\displaystyle vNx}$${\displaystyle uv^{n}wx^{n}y}$${\ estilo de visualización n = 0}$${\ estilo de visualización 2}$