En esta semana vamos a conocer un poco sobre el lema de bombeo de Pumping y también sobre la Forma Normal de Greibach.

PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES REGULARES.

Si L es un lenguaje finito, es regular y se podrá construir un autómata finito o una expresión regular para ellos de forma sencilla. También, si L es especificado ya sea por medio de un autómata finito o una expresión regular, la respuesta es obvia. Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la búsqueda exhaustiva de una expresión regular o un autómata finito puede resultar inútil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estén presentes en los lenguajes regulares.
Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un DFA M=(Q, S, q0, d, F), donde Q contiene n estados. Si L(M) es infinito, podremos encontrar cadenas cuya longitud sea mayor que n. Supongamos que w= a1, a2, ...,an+1 es una de las cadenas de longitud n+1 que pertenecen a L(M).

Si tuviéramos
q1= d(q0, a1)
q2= d(q1, a2)
y así sucesivamente, obtendríamos los n+1 estados, q1, q2 ,..., qn+1. Puesto que Q contiene sólo n estados , los qi no serán todos distintos. En consecuencia, para algunos índices j y k, con 1£ j £n+1, se obtendrá que qj= qk. Por lo tanto, tendremos un ciclo en el camino que parte de q0 hasta un estado de aceptación según se muestra en la siguiente figura.

Puesto que j< w="uvx," l="{a" an =" uvx" n2 =" uvx">

PUMPING LEMMA PARA LENGUAJES LIBRES DE CONTEXTO.

El planteamiento formal del lema de bombeo (Pumping Lemma en inglés) para CFL’s es el siguiente: Sea L un lenguaje libre de contexto que no contiene e. Entonces existe un entero k para el cual, si z Î L y ½z½>k , entonces z se puede volver a escribir como z = uvwxy con las propiedades siguientes:

1. ½vwx½£ k.
2. Al menos v o x no es e.
3. uvi wxi y Î L para todo i ³ 0.

Al igual que el lema de bombeo para lenguajes regulares, el lema de bombeo para lenguajes libres de contexto nos proporciona la posibilidad de probar si ciertos lenguajes no son libres de contexto, por tanto, utilizaremos el mismo planteamiento que en el caso de los lenguajes regulares.
Supongamos que L ={ai bj j= i2} es libre de contexto, entonces se puede aplicar el lema de bombeo y por tanto habrá un k que satisfaga las condiciones del lema. Consideremos z= ak bk2.
Desde luego, z Î L y ½z½>k. Por tanto, z se puede descomponer en z=uvwxy y se puede asegurar que uvi wxi y Î L para todo i ³ 0, tal que ½vxz½>1 y ½vwx½£ k. Obsérvese que, si v= ar bs para algún r y s, entonces vi= (ar bs) i y, por tanto, uvi wxi y tiene b’s antes de a’s con lo que no puede pertenecer a L. De forma similar, si x= ar bs, tampoco pueden ser bombeados. Por lo que debemos obtener que:
v= ar y x= as o
v= br y x= bs o también
v= ar y x= bs

para algún valor de r y s. En el primer caso se tiene uv2 wx2 y= ak+r+sbk2

En el segundo caso tenemos uv2 wx2 y= akbk2+r+s
En ambos casos, cuando al menos uno de los dos r o s, son ³ 1 (como se requiere en el lema de bombeo), la cadena resultante no puede pertenecer a L. En el tercer caso, se obtendrá uvi wxi y= ak+(i-1)rbk2+(i-1)s el cual no pertenece a L para toda i a excepción de un número finito. Por tanto, L no puede ser libre de contexto puesto que para él no se cumple el lema de bombeo.


Forma Normal de Greibach

Definición: Sea G = (Vn, Vt, S,P) una gramática libre de contexto. Diremos que G respeta la forma normal de Greibach (FN Greibach) si toda regla de P es de la forma:
A→ a Z, donde A∈Vn , a∈Vt , y Z∈Vn*

El siguiente teorema relaciona los Lenguajes LC y las GLC en Forma Normal de Greibach.

Teorema: Cualquier Lenguaje libre de contexto puede ser generado por una gramática que respeta la forma normal de Greibach.

Algoritmo [esquema] para GLC G à FN Greibach
Entrada: G=(Vn,Vt, S ,P),
Salida: G’=(Vn’,Vt, S ,P’) en FN Greibach
Eliminar la recursión a izquierda (ej: A→Aa) sustituyendo cada sublenguaje generado recursivamente por un conjunto de reglas equivalente, pero sin recursión.

Agregar nuevas reglas de reescritura y no terminales para llevar las reglas existentes a la forma de Greibach:
Reemplazar A∈Vn en cada α →β, de a una por vez, para introducir terminales a izquierda.
Reemplazar cada a∈Vt que no está en la parte izquierda de β por nuevos A’ ∈Vn (esto deja solo no terminales a derecha).


Ejemplo: aplicando FNGreibach (1)

G=(Vn,Vt, S ,P), Vn ={S , A,B}, Vt={a,b,c},
P={S → ABB, A→ Aab, B→ Abc}

Reescribamos para simplificar lectura:
P={ S→AB, S→B, A→Aa, A→b, B→Ab, B→c }

Esta gramática tiene la regla con recursión a izq.:
A→ Aa
Esta regla junto con “A→b” genera secuencias de la forma ba*. Puede transformarse en una secuencia equivalente reemplazando las reglas anteriores por:
{ A→b, A→bD, D→aD, D→a}
Se tiene así:


Ejemplo: aplicando FNGreibach (2)
P’={ S→AB, S→B, A→b, A→bD,
D→aD, D→a B→Ab, B→c }
Ahora es necesario realizar reemplazos para dejar los terminales del lado izquierdo en cada parte derecha de una regla.

Podemos comenzar reemplazando el no terminal B en la parte derecha de una regla. Podemos comenzar reemplazando B en la parte derecha de las reglas de P’. En este caso solo es estrictamente necesario en S → B, obteniendo:

P’’={ S →AB, S→Ab, S→c, A→b, A→bD, D→aD, D→a, B→ Ab, B→c }

Ej.: aplicando FNGreibach (3)
P’’={S →AB, S→Ab, S→c, A→b, A→bD, D→aD, D→a, B→ Ab, B→ c}

Análogamente, podemos reemplazar las apariciones del no terminal A. Obtenemos:
P’’’={ S→bB, S→ bDB, S→ bb, S→ bDb, S→ c, D→aD ,D→ a,B→bb, B→ bDb, B→ c}

Ej.: aplicando FNGreibach (4)
P’’’={S→bB, S→ bDB, S→ bb, S→ bDb, S→ c, D→aD , D→ a,B→bb, B→ bDb, B→c }

Pero no toda regla es de la forma A→ a Z, Z∈Vn*. Entonces finalmente introducimos una nueva regla E →b para respetar la FNGreibach:

P’’’’={ S→bB, S→ bDB, S→ bE, S→ bDE, S→ c, D→aD, D→a, B→bE, B→ bDE, B→ c, E→b}
P’’’’={ S→bBbDBbEbDEc, D→aDa, B→bEbDEc, E→b}

Ventaja de FNGreibach: se conoce que cada cadena de longitud n es derivable en n pasos.

Y para finalizar, les dejo una pequeñisima reseña de la mujer creadora de la FNG.

Sheila Greibach
Nacida en New York (1939), obtuvo su doctorado en 1963 en la Univ. de Harvard. Actualmente trabaja en el Dep. de Cs. de la Computación de la UCLA (EEUU). Si usted desea comunicarse con ella puede hacerlo a la siguiente direccion de email: greibach@cs.ucla.edu.

Les ruego disculpas, ya que al parecer las fuentes disponibles al momento de crear las entradas, no reconocen ciertos símbolos que se encuentran en el cuerpo del artículo.
Y también me gustaría decirles, que si alguien conoce cómo hacer para solucionar este problema, que me lo haga saber mediante un mensaje en este blog.
Además me gustaría subir el documento pero creo que esto no es factible. Si alguien lo quisiera solo hagame saberlo enviandome un email a racosta2001@hotmail.com.