Lema del bombeo para gramáticas independientes del contexto
# Lema del bombeo para gramáticas independientes del contexto

Viene de Lema del bombeo:

Sea ${\mbox{L}}\,$ un lenguaje libre de contexto. Entonces existe una constante $n\in {\mbox{N}}$ tal que para toda palabra $x\in {\mbox{L}}$, con $|x|\geq n\,$, existe una descomposición $x=yzuvw\,$ tal que:

* $|zuv|\leq n\,$
* $|zv|>0\,$
* $\forall i\geq 0,x=yz^{i}uv^{i}w\in {\mbox{L}}\,$

(Indicando $|x|\,$ la longitud de la palabra, y $x^{i}\,$ la repetición de la palabra $x\,$ $i\,$ veces).

Este teorema implica que en todo lenguaje libre de contexto, para toda palabra suficientemente larga ($|x|\geq n\,$), se pueden encontrar una o dos subcadenas izquierda ($z\,$) y derecha ($v\,$), cuya longitud conjunta es a lo sumo n ($|zuv|\leq n\,$), que pueden o bien eliminarse, o bien repetirse simultáneamente las veces que se desee ($yz^{i}uv^{i}w\,$), obteniendo de dicha forma palabras que también pertenecen al lenguaje.

El contrarrecíproco de este teorema se puede aplicar para demostrar que un lenguaje no es libre de contexto:

* Suponemos $n\,$ la constante de bombeo.
* Escogemos cuidadosamente una determinada palabra del lenguaje tal que $|x|\geq n\,$
* Si toda descomposición de $x$, tal que $|zuv|\leq n,|zv|>0\,$ y $yz^{i}uv^{i}w,i\geq 0\,$ no pertenece al lenguaje para algún $i\in \mathbb {N}$, entonces dicho lenguaje no es libre de contexto.
