Lema de bombeo en la teoría de la computación – Part 1

Hay dos lemas de bombeo, que se definen para
1. Lenguajes regulares y
2. Contexto: lenguajes libres
 
Lema de bombeo para lenguajes regulares
Para cualquier lenguaje regular L, existe un entero n, tal que para todo x ∈ L con |x| ≥ n, existe u, v, w ∈ Σ∗, tal que x = uvw, y
(1) |uv| ≤ norte
(2) |v| ≥ 1
(3) para todo i ≥ 0: uv ⁱ w ∈ L
 
En términos simples, esto significa que si se ‘bombea’ una string v, es decir, si se inserta v cualquier número de veces, la string resultante aún permanece en L .
 
Pumping Lemma se utiliza como prueba de la irregularidad de un idioma. Así, si una lengua es regular, siempre satisface el lema de bombeo. Si existe al menos una cuerda hecha de bombeo que no está en L, entonces L seguramente no es regular.
Lo contrario de esto puede no ser siempre cierto. Es decir, si Pumping Lemma se cumple, no significa que el lenguaje sea regular.

Por ejemplo, probemos L ₀₁ = {0 ⁿ 1 ⁿ | n ≥ 0} es irregular.
Supongamos que L es regular, luego bombeando Lemma se siguen las reglas dadas anteriormente.
Ahora, sea x ∈ L y |x| ≥ n. Entonces, por Pumping Lemma, existe u, v, w tal que (1) – (3) se cumple.
 
Mostramos que para todo u, v, w, (1) – (3) no se cumple.
Si (1) y (2) se cumplen, entonces x = 0 ⁿ 1 ⁿ = uvw con |uv| ≤ ny |v| ≥ 1.
Entonces, u = 0 ^a , v = 0 ^b , w = 0 ^c 1 ⁿ donde : a + b ≤ n, b ≥ 1, c ≥ 0, a + b + c = n
Pero, entonces (3) falla para i = 0
uv ⁰ w = uw = 0 ^a0 ^c 1 ⁿ = 0 ^{a + c} 1 ⁿ ∉ L, ya que a + c ≠ n. Lema de bombeo para lenguajes libres de contexto (CFL) El lema de bombeo para CFL establece que para cualquier lenguaje L libre de contexto, es posible encontrar dos substrings que se pueden ‘bombear’ cualquier cantidad de veces y seguir estando en el mismo idioma. Para cualquier idioma L, dividimos sus strings en cinco partes y bombeamos la segunda y cuarta substring. Pumping Lemma, aquí también, se usa como una herramienta para probar que un idioma no es CFL. Porque, si alguna string no satisface sus condiciones, entonces el lenguaje no es CFL. Entonces, si L es una LFC, existe un entero n, tal que para todo x ∈ L con |x| ≥ n, existe u, v, w, x, y ∈ Σ∗, tal que x = uvwxy, y

 
 

(1) |vwx| ≤ n
(2) |vx| ≥ 1
(3) para todo i ≥ 0: uv ⁱ wx ⁱ y ∈ L

Para el ejemplo anterior, 0 ⁿ 1 ⁿ es CFL, ya que cualquier string puede ser el resultado de bombear en dos lugares, uno para 0 y otro para 1.
Probemos, L ₀₁₂ = {0 ⁿ 1 ⁿ 2 ⁿ | n ≥ 0} no está libre de contexto.
Supongamos que L es independiente del contexto, luego bombeando Lemma, se siguen las reglas dadas anteriormente.
Ahora, sea x ∈ L y |x| ≥ n. Entonces, por Pumping Lemma, existe u, v, w, x, y tal que (1) – (3) se cumple.
Mostramos que para todo u, v, w, x, y (1) – (3) no se cumplen.
 
Si (1) y (2) se cumplen, entonces x = 0 ⁿ 1 ⁿ 2 ⁿ = uvwxy con |vwx| ≤ ny |vx| ≥ 1.
(1) nos dice que vwx no contiene ni 0 ni 2. Por lo tanto, vwx no tiene 0 o vwx no tiene 2. Por lo tanto, tenemos dos casos a considerar.
Supongamos que vwx no tiene ceros. Por (2), vx contiene un 1 o un 2. Por lo tanto, uwy tiene ‘n’ 0 y uwy tiene menos de ‘n’ 1 o menos de ‘n’ 2.
Pero (3) nos dice que uwy = uv ⁰ wx ⁰ y ∈ L.
Entonces, uwy tiene el mismo número de 0, 1 y 2, lo que nos da una contradicción. El caso donde vwx no tiene 2 es similar y también nos da una contradicción. Por lo tanto, L no está libre de contexto.

 
Fuente: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introducción a la teoría de autómatas, lenguajes y computación.
 
Este artículo ha sido aportado por Nirupam Singh .
  
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.