Lema de bombeo

Curso Básico de Computación
6 Propiedades de los lenguajes libres de contexto

Feliú Sagols Troncoso
Matemáticas
CINVESTAV-IPN


2010

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

1 / 46

6 Propiedades de los lenguajes libres de contexto
6.1 El Lema de Bombeo para LLC
El lema de Bombeo para LLC nos dice que siempre existe dossubcadenas cortas muy juntas que se pueden repetir, ambas el mismo
número de veces. El enunciado formal es el siguiente:

Lema (6.1 Lema de Bombeo para lenguajes libres de
contexto)
Sea L un LLC. Entonces existe una constante n, que depende sólo de
L, tal que si z ∈ L y |z| ≥ n, entonces z = uvwxy tal que
1) |vx | ≥ 1,
2) |vwx | ≤ n y
3) Para toda i ≥ 0, uv i wx i y ∈ L
Curso Básico deComputación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

2 / 46

Demostración:
Sea G una grámatica en su forma normal de Chomsky que genera a
L − {ǫ}. Observe que si z ∈ L(G) y z es larga, entonces cualquier
árbol de derivación para z debe contener un camino largo. Más
precisamente, se demuestra por inducción sobre i que si el árbol de
derivación de unapalabra generada por la grámatica en la forma
normal de Chomsky no tiene caminos de longitud más grande que i
entonces la longitud de la palabra no es más grande que 2i−1 .
G tiene k variables y sea n = 2k , Si z ∈ L(G) y |z| ≥ n, entonces
como |z| > 2k−1 , cualquier árbol de derivación para z debe tener un
camino de longitud al menos k + 1. Pero tal camino tiene al menos
k + 2 vértices, todosexcepto el último son etiquetados por variables.
Así, existen algunas variables que aparecen dos veces en el camino.

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

3 / 46

De hecho podemos decir más. Algunas variables deben aparecer dos
veces cerca del final del camino. En particular, sea P el camino más
largo del árbol. Entonces existendos vértices v1 y v2 en el camino
que satisfacen las siguientes condiciones:
1
Ambos vértices v1 y v2 tienen la misma etiqueta, digamos A.
2
El vértice v1 está más cerca de la raíz que v2
3
La porción del camino de v1 a cualquier hoja es de longitud a lo
más k + 1.
Siempre se pueden encontrar v1 y v2 .

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres decontexto

2010

4 / 46

Ahora el subárbol T1 con raíz v1 representa la derivación de una
subpalabra de longitud al menos 2k . Esto es verdad porque puede que
no haya caminos en T1 de longitud más grande que k + 1, como P
fue el camino de longitud más grande en el árbol entero. Sea z1 lo
que produce el subárbol T1 . Si T2 es el subárbol generado por el
vértice v2 , y z2 lo que ésteproduce, entonces se puede escribir z1
como z3 z2 z4 . Además, z3 y z4 no pueden ser ambos ǫ, ya que la
primera producción usada en la derivación de z1 es de la forma
A → BC para algunas variables B y C . El subárbol T2 debe estar
completamente dentro del subárbol generado por B o del subárbol
generado por C , como se ilustra a continuación.

Curso Básico de Computación (Matemáticas)6 Propiedadesde los lenguajes libres de contexto

2010

5 / 46

A

C

B

A

B
v1

B

b

a

A

B

b

C
v2

B

b

A
Camino P

a
b
z

3

z

= bb

2

z

1

= a

z

4

=

ε

= bba

z = bbbaba
(a)

Árbol

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

6 / 46

A

B
C

b

B

vA

2

a
b
(b) Subárbol T1

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

7 / 46

A

(c) Subárbol T2

a

Curso Básico de Computación (Matemáticas)6 Propiedades de los lenguajes libres de contexto

2010

8 / 46

Se sabe que A

∗
=⇒
G

∗

z3 Az4 y A ⇒ z2 , donde |z3 z2 z4 | ≤ 2k = n.
∗
=⇒

i
i
Pero se...