title: Lema del bombeo para gramáticas independientes del contexto
text: # 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.