Ver el código de «Lema del bombeo para lenguajes libres del contexto»

En ciencia de la computación, en particular en la teoría de [[lenguajes formales]], el lema del bombeo para lenguajes libres del contexto, también conocido como lema de Bar-Hille, es un lema que brinda una propiedad compartida por todos los lenguajes libres del contexto y generaliza el [[lema del bombeo para lenguajes regulares]]. Como el lema del bombeo no garantiza que el lenguaje sea libre del contexto, existen condiciones necesarias más fuertes, como el lema de Ogden.

== Declaración formal ==
[[Archivo:Pumping_lemma_for_context-free_languages.svg|miniaturadeimagen|300x300px|Idea de la demostración: ''S''i s es suficie''n''temente larga, su [[árbol de derivación]] w.r.t. una [[formal normal de Chomsky]] debe contener algún no-terminal N dos veces en algún camino del árbol (imagen superior). Repitiendo ''n'' veces la parte de la derivación N ⇒...⇒ ''vNx'' se obtiene una derivación para uvnwxny (imágenes situadas abajo a izquierda y a la derecha respectivamente para n=0 y 2).]]
''Si un lenguaje L es libre del contexto, entonces existe un entero p >= 1 (llamado longitud de bombeo) tal que toda cadena s en L que tiene una longitud de p o más símbolos (|s| > p) puede ser escrita como:''
: ''s'' = ''uvwxy''
''Con subcadenas u, v, w, x y y, tal que:''
: 1. |vwx| ≤ ''p''
: 2. |vx| ≥ 1<br>
: 3. ''uv<sup>n</sup>wx<sup>n</sup>y'' &isin; ''L'' para todo ''n'' ≥ 0
Debajo está una expresión formal del Lema de Bombeo.

<math>
\begin{array}{l}                                                                                                                                       
(\forall  L\subseteq \Sigma^*)  \\                                                                                                                     
\quad      (\mbox{ libre del contexto }(L) \Rightarrow \\                                                                                                           
\quad      ((\exists p\geq 1) ((\forall s\in L) ((|s|\geq p) \Rightarrow \\                                                                           
\quad ((\exists u,v,w,x,y \in \Sigma^*) (s=uvwxy \land |vwx|\leq p \land |vx|\geq 1 \land (\forall n \geq 0)                                                              
(uv^nwx^ny\in L)))))))                                                                                                                   
\end{array} 
</math>

== Explicación y declaración informal ==
El lema del bombeo para lenguajes libres del contexto (llamado solo “el lema del bombeo” en el resto de este artículo) describe una propiedad que todos los lenguajes libres del contexto garantizan cumplir.

La propiedad es una propiedad de todas las cadenas en el lenguaje que son de longitud al menos p, donde p es una constante-llamada longitud del bombeo- que varía entre lenguajes libres del contexto.

Digamos que s es una cadena de longitud al menos p que está en el lenguaje.

El lema del bombeo establece que s puede ser dividida en 5 subcadenas, s=uvwxy, donde vx es no vacío y la longitud de vwx es como máximo p, tal que repitiendo v y x cualquier (y el mismo) número de veces en s produce una cadena que está todavía en el lenguaje (esto es posible y a menudo útil repetir cero veces, lo cual elimina v y x de la cadena). Este proceso de “bombear” copias adicionales de v y x es lo que le da al lema del bombeo su nombre.

Los [[lenguajes finitos]] (los cuales son regulares y por lo tanto libres del contexto) cumplen el lema del bombeo trivialmente haciendo p igual a la longitud de la cadena de mayor longitud en L más uno. Como no hay cadenas de esta longitud el lema del bombeo no es violado.

== Uso del lema ==
El lema del bombeo es frecuentemente usado para probar que un lenguaje dado L no es libre del contexto, mostrando que arbitrariamente largas cadenas s están en L que no pueden ser “bombeadas” sin producir cadenas fuera de L.

Por ejemplo, el lenguaje ''L'' = { ''a''<sup>''n''</sup>''b''<sup>''n''</sup>''c''<sup>''n''</sup> | ''n'' > 0 } se puede mostrar que no es libre del contexto usando el lema del bombeo en una [[reducción al absurdo]]. Primero, se asume que L es libre del contexto. Por el lema del bombeo, existe un entero p que es la longitud de bombeo del lenguaje L. Sea la cadena ''s'' = ''a''<sup>''p''</sup>''b''<sup>''p''</sup>''c''<sup>''p''</sup> in ''L''. El lema del bombeo plantea que s puede ser escrito en la forma s=uvwxy, donde u,v,w,x,y son subcadenas, tal que |vwx| ≤ p, |vx| ≥ 1, ''uv''<sup>''i''</sup>''wx''<sup>''i''</sup>''y'' ∈ L para todo entero i  ≥ 0. Mediante la selección de s y el hecho de que |vwx| ≤ p, es fácil ver que la subcadena vwx no puede contener más de 2 símbolos distintos. Luego, tenemos una de 5 posibilidades para vwx:
# ''vwx'' = a<sup>''j''</sup> ''P''ara algún j ≤ p.
# ''vwx'' = a<sup>''j''</sup>b<sup>''k''</sup> ''P''ara algún j y k con j+k ≤ p.
# ''vwx'' = b<sup>''j''</sup> ''P''ara algún j ≤ p.
# ''vwx'' = b<sup>''j''</sup>c<sup>''k''</sup> ''P''ara algún j y k con j+k ≤ p.
# ''vwx'' = c<sup>''j''</sup> ''P''ara algún j ≤ p.
Para cada caso, es fácilmente verificable que ''uv''<sup>''i''</sup>''wx''<sup>''i''</sup>''y'' no contiene iguales números de cada letra para cualquier i ≠ 1. Por lo tanto, ''uv''<sup>2</sup>''wx''<sup>2</sup>''y'' no tiene la forma ''a''<sup>''i''</sup>''b''<sup>''i''</sup>''c''<sup>''i''</sup>. Esto contradice la definición de L. Luego, la asunción inicial de que  L es libre del contexto es falsa.

Mientras que el lema del bombeo es a menudo una útil herramienta para probar que un lenguaje dado no es libre del contexto, este no ofrece una caracterización completa de los lenguajes libres del contexto. Si un lenguaje no satisface la condición dada por dicho lema, se establece que no es libre del contexto.

Por otra parte, existen lenguajes que no son libres del contexto, y, sin embargo, satisfacen la condición dada por el lema del bombeo, por ejemplo ''L'' = { ''b''<sup>''j''</sup>''c''<sup>''k''</sup>''d''<sup>''l''</sup> | ''j'', ''k'', ''l'' &isin; ℕ } 
∪ { ''a''<sup>''i''</sup>''b''<sup>''j''</sup>''c''<sup>''j''</sup>''d''<sup>''j''</sup> | ''i'', ''j'' ∈ ℕ, ''i''≥1 }: para ''s''=''b''<sup>''j''</sup>''c''<sup>''k''</sup>''d''<sup>''l''</sup> con por ejemplo ''j''≥1 se selecciona ''vwx'' que consiste solo de ''b''’s, for ''s''=''a''<sup>''i''</sup>''b''<sup>''j''</sup>''c''<sup>''j''</sup>''d''<sup>''j''</sup> se selecciona ''vwx'' que consiste solo de ''a''’s; en ambos casos todas las cadenas bombeadas están todavía en L.

== Referencias ==
{{listaref}}
* Barra-Hillel, {{Cita libro|apellidos=Y. Bar-Hillel|título=Language and Information: Selected Essays on their Theory and Application|año=1964|editorial=Addison-Wesley|isbn=0201003732|páginas=116–150|oclc=783543642}}; {{Cita publicación|título=On formal properties of simple phrase-structure grammars|enlaceautor=Yehoshua Bar-Hillel|apellidos2=[[Micha Perles]]|publicación=Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung|volumen=14|número=2|páginas=143–172|apellidos3=[[Eli Shamir]]|año=1961}};  (1961). "En propiedades formales de frase sencilla-gramáticas de estructura". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung.  (2): 143@–172.  &#x2014; Reprinted En: Y.  (1964). Lengua e Información: Seleccionó Ensayos en su Teoría y Aplicación. Addison-Wesley serie en lógica. Addison-Wesley. pp.      
* {{Cita libro|apellidos=[[Michael Sipser]]|título=Introduction to the Theory of Computation|año=1997|editorial=PWS Publishing|isbn=0-534-94728-X|url=https://archive.org/details/introductiontoth00sips}} (1997).  PWS Publicando.    Sección 1.4: Nonregular Lenguas, pp. 77@–83. Sección 2.3: No-contexto-Lenguas libres, pp. 115@–119.
{{Control de autoridades}}
[[Categoría:Lenguajes formales]]
[[Categoría:Lemas (matemáticas)]]