Lema de bombeo para lenguajes libres de contexto

Tipo de lema de bombeo

En informática , en particular en teoría del lenguaje formal , el lema de bombeo para lenguajes libres de contexto , también conocido como 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 para los lenguajes regulares .

El lema de bombeo puede utilizarse para construir una refutación por contradicción de que un lenguaje específico no es libre de contexto. Por el contrario, el lema de bombeo no es suficiente para garantizar que un lenguaje sea libre de contexto; existen otras condiciones necesarias, como el lema de Ogden o el lema de intercambio .

Declaración formal

Idea de prueba: Si es suficientemente largo, su árbol de derivación con respecto a una gramática de la forma normal de Chomsky debe contener algún no terminal dos veces en algún camino del árbol (imagen superior). Al repetir la parte de derivación ⇒...⇒ se obtiene una derivación para (imagen inferior izquierda y derecha para y , respectivamente). ${\displaystyle s}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle vNx}$ ${\displaystyle uv^{n}wx^{n}y}$ ${\displaystyle n=0}$ ${\displaystyle 2}$

Si un lenguaje es libre de contexto, entonces existe algún entero (llamado "longitud de bombeo") ^[2] tal que cada cadena en que tenga una longitud de o más símbolos (es decir, con ) se puede escribir como ${\displaystyle L}$ ${\displaystyle p\geq 1}$ ${\displaystyle s}$ ${\displaystyle L}$ ${\displaystyle p}$ ${\displaystyle |s|\geq p}$

${\displaystyle s=uvwxy}$

con subcadenas y , tales que ${\displaystyle u,v,w,x}$ ${\displaystyle y}$

1. , ${\displaystyle |vx|\geq 1}$

2. , y ${\displaystyle |vwx|\leq p}$

3. para todos . ${\displaystyle uv^{n}wx^{n}y\in L}$ ${\displaystyle n\geq 0}$

A continuación se muestra una expresión formal del lema de bombeo.

${\displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{context free}}(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 |vx|\geq 1\land |vwx|\leq p\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))))))\end{array}}}$

Declaración informal y explicación

El lema de bombeo para lenguajes libres de contexto (llamado simplemente "el lema de bombeo" en el resto de este artículo) describe una propiedad que se garantiza que tienen todos los lenguajes libres de contexto.

La propiedad es una propiedad de todas las cadenas en el lenguaje que tienen una longitud de al menos , donde es una constante, llamada longitud de bombeo , que varía entre lenguajes independientes del contexto. ${\displaystyle p}$ ${\displaystyle p}$

Say es una cadena de longitud al menos la que está en el lenguaje. ${\displaystyle s}$ ${\displaystyle p}$

El lema de bombeo establece que se puede dividir en cinco subcadenas, , donde no está vacío y la longitud de es como máximo , de modo que repetir y la misma cantidad de veces ( ) en produce una cadena que todavía está en el lenguaje. A menudo es útil repetir cero veces, lo que elimina y de la cadena. Este proceso de "bombeo" con copias adicionales de y es lo que le da al lema de bombeo su nombre. ${\displaystyle s}$ ${\displaystyle s=uvwxy}$ ${\displaystyle vx}$ ${\displaystyle vwx}$ ${\displaystyle p}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle x}$

Los lenguajes finitos (que son regulares y, por lo tanto, independientes del contexto) obedecen el lema de bombeo de manera trivial al tener igual a la longitud máxima de la cadena en más uno. Como no hay cadenas de esta longitud, no se viola el lema de bombeo. ${\displaystyle p}$ ${\displaystyle L}$

Uso del lema

El lema de bombeo se utiliza a menudo para demostrar que un lenguaje dado L no es libre de contexto, mostrando que existen cadenas arbitrariamente largas s en L que no se pueden "bombear" sin producir cadenas fuera de L.

Por ejemplo, si es infinito pero no contiene una progresión aritmética (infinita) , entonces no es independiente del contexto. En particular, ni los números primos ni los números cuadrados son independientes del contexto. ${\displaystyle S\subset \mathbb {N} }$ ${\displaystyle L=\{a^{n}:n\in S\}}$

Por ejemplo, se puede demostrar que el lenguaje no es libre de contexto utilizando el lema de bombeo en una prueba por contradicción . Primero, supongamos que L es libre de contexto. Por el lema de bombeo, existe un entero p que es la longitud de bombeo del lenguaje L. Consideremos la cadena en L. El lema de bombeo nos dice que s se puede escribir en la forma , donde u, v, w, x e y son subcadenas, tales que , , y para cada entero . Por la elección de s y el hecho de que , se ve fácilmente que la subcadena vwx no puede contener más de dos símbolos distintos. Es decir, tenemos una de cinco posibilidades para vwx : ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$ ${\displaystyle s=a^{p}b^{p}c^{p}}$ ${\displaystyle s=uvwxy}$ ${\displaystyle |vx|\geq 1}$ ${\displaystyle |vwx|\leq p}$ ${\displaystyle uv^{i}wx^{i}y\in L}$ ${\displaystyle i\geq 0}$ ${\displaystyle |vwx|\leq p}$

1. ${\displaystyle vwx=a^{j}}$Para algunos . ${\displaystyle j\leq p}$
2. ${\displaystyle vwx=a^{j}b^{k}}$para un poco de j y k con ${\displaystyle j+k\leq p}$
3. ${\displaystyle vwx=b^{j}}$Para algunos . ${\displaystyle j\leq p}$
4. ${\displaystyle vwx=b^{j}c^{k}}$para algunos j y k con . ${\displaystyle j+k\leq p}$
5. ${\displaystyle vwx=c^{j}}$Para algunos . ${\displaystyle j\leq p}$

En cada caso, se verifica fácilmente que no contiene cantidades iguales de cada letra para ningún . Por lo tanto, no tiene la forma . Esto contradice la definición de L . Por lo tanto, nuestra suposición inicial de que L es independiente del contexto debe ser falsa. ${\displaystyle uv^{i}wx^{i}y}$ ${\displaystyle i\neq 1}$ ${\displaystyle uv^{2}wx^{2}y}$ ${\displaystyle a^{i}b^{i}c^{i}}$

En 1960, Scheinberg demostró que no es libre de contexto utilizando un precursor del lema de bombeo. ^[3] ${\displaystyle L=\{a^{n}b^{n}a^{n}|n>0\}}$

Si bien el lema de bombeo es a menudo una herramienta útil para demostrar que un lenguaje dado no es libre de contexto, no proporciona una caracterización completa de los lenguajes libres de contexto. Si un lenguaje no satisface la condición dada por el lema de bombeo, hemos establecido que no es libre de contexto. Por otro lado, hay lenguajes que no son libres de contexto, pero que aún así satisfacen la condición dada por el lema de bombeo, por ejemplo

${\displaystyle L=\{b^{j}c^{k}d^{l}|j,k,l\in \mathbb {N} \}\cup \{a^{i}b^{j}c^{j}d^{j}|i,j\in \mathbb {N} ,i\geq 1\}}$

para s = b ^j c ^k d ^l con p. ej. j ≥1 elija vwx para que consista solo en b ' s, para s = a ⁱ b ^j c ^j d ^j elija vwx para que consista solo en a ' s; en ambos casos todas las cadenas bombeadas todavía están en L . ^[4]

Referencias

1. Kreowski, Hans-Jörg (1979). "Un lema de bombeo para lenguajes de grafos libres de contexto". En Claus, Volker; Ehrig, Hartmut ; Rozenberg, Grzegorz (eds.). Gramáticas de grafos y su aplicación a la informática y la biología. Apuntes de clase en informática. Vol. 73. Berlín, Heidelberg: Springer. pp. 270–283. doi :10.1007/BFb0025726. ISBN 978-3-540-35091-0.
2. Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras (PDF) . Serie de monografías CRM. Vol. 27. Providence, RI: American Mathematical Society . pág. 90. ISBN. 978-0-8218-4480-9.Zbl 1161.68043  .(Ver también [www-igm.univ-mlv.fr/~berstel/ sitio web de Aaron Berstel)
3. Stephen Scheinberg (1960). "Nota sobre las propiedades booleanas de los lenguajes libres de contexto" (PDF) . Información y control . 3 (4): 372–375. doi : 10.1016/s0019-9958(60)90965-7 .Aquí: Lema 3, y su uso en las páginas 374-375.
4. John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación. Addison-Wesley. ISBN 0-201-02988-X.Aquí: secc.6.1, p.129

• Bar-Hillel, Y .; Micha Perlés ; Eli Shamir (1961). "Sobre las propiedades formales de las gramáticas de estructura sintagmática simple". Zeitschrift für Phonetik, Sprachwissenschaft y Kommunikationsforschung . 14 (2): 143-172.— Reimpreso en: Y. Bar-Hillel (1964). Lenguaje e información: ensayos seleccionados sobre su teoría y aplicación . Serie Addison-Wesley sobre lógica. Addison-Wesley. págs. 116–150. ISBN 0201003732.OCLC 783543642  .
• Michael Sipser (1997). Introducción a la teoría de la computación. PWS Publishing. ISBN 0-534-94728-X.Sección 1.4: Lenguajes no regulares, págs. 77–83. Sección 2.3: Lenguajes no libres de contexto, págs. 115–119.