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.

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

3. uvⁿwxⁿy ∈ L para todo n ≥ 0

Debajo está una expresión formal del Lema de Bombeo.

${\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^{n}wx^{n}y\in L)))))))\end{array}}$

Explicación y declaración informal

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ⁿbⁿcⁿ | 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^pb^pc^p 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ⁱwxⁱ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^j Para algún j ≤ p.
vwx = a^jb^k Para algún j y k con j+k ≤ p.
vwx = b^j Para algún j ≤ p.
vwx = b^jc^k Para algún j y k con j+k ≤ p.
vwx = c^j Para algún j ≤ p.

Para cada caso, es fácilmente verificable que uvⁱwxⁱy no contiene iguales números de cada letra para cualquier i ≠ 1. Por lo tanto, uv²wx²y no tiene la forma aⁱbⁱcⁱ. 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^jc^kd^l | j, k, l ∈ ℕ } ∪ { aⁱb^jc^jd^j | i, j ∈ ℕ, i≥1 }: para s=b^jc^kd^l con por ejemplo j≥1 se selecciona vwx que consiste solo de b’s, for s=aⁱb^jc^jd^j se selecciona vwx que consiste solo de a’s; en ambos casos todas las cadenas bombeadas están todavía en L.

Lema del bombeo para lenguajes libres del contexto

Explicación y declaración informal

Uso del lema

Referencias

Related Articles