Sunday, February 05, 2006

Lema del bombeo y forma normal de Greybach

El lema de bombeo se define de la siguiente forma:

Sea L un lenguaje regular infinito. Entonces hay una constante n de forma que, sí w es una cadena de L cuya longitud es ³ n, se tiene que w=uvx, siendo uvixÎ L para todo i ³ 0, con v ³ 1 y uv £ n.

El lema de bombeo facilita una forma de determinar si un lenguaje es regular; de esta forma se podrá decir si es finito y por ello se podrá construir un autómata finito o una expresión regular dada la conexión que existe entre ambos. Recordemos que un lenguaje regular es generado por una expresión regular (para mayor comprensión del tema ver la sección de lenguajes regulares de este capítulo). Para demostrar que un lenguaje no es regular, se mostrará que, cualquier valor n lo bastante grande, se tendrá al menos una cadena de longitud n o mayor que falle al ser "bombeada".

Por ejemplo: Considérese el lenguaje L={a i i ³ 1}
Toda cadena L debe tener una longitud que sea un cuadrado perfecto. Supongamos que L es regular y sea n la constante dada en el lema de bombeo. Obsérvese que an Î L y que, por el lema de bombeo, tenemos an = uvx de forma que 1£ v £ n y uvix Î L para todo i ³ 1. Entonces se obtiene que:


n2 = uvx < uv2x
£ n2 + n < (n+1)2


El lema de bombeo dice básicamente lo siguiente:

Si un lenguaje infinito es regular, este puede ser definido por un autómata finito.
El autómata tiene un numero finito de estados. (digamos, p)
Como el lenguaje es infinito, algunas cadenas en el lenguaje pasarán mas de una vez por algun estado. (estas serán las cadenas que tengan un largo mayor que el número de estados del autómata).
Para que una cadena como la anterior pase mas de una vez por el mismo estado, el autómata debetener un ciclo en alguna parte.
Al repetir el ciclo cuantas veces queramos, el generaremos cademas que tambien estan en el lenguaje


Es decir, la longitud de uv2x se encuentra, estrictamente, entre cuadrados perfectos consecutivos y, por tanto, no es un cuadrado perfecto. Luego uv2x no puede pertenecer a L. Es decir, L no puede ser regular.

Para qué sirve?Lo anterior es sencillo, verdad?... incluso es muy lógico. Entonces, dónde radica la importancia del lema de bombeo?... Si analizamos lo anterior, vemos que:
Si un lenguaje es regular (e infinito), ENTONCES cumple el lema del bombeo
O lo que es lo mismo:
Si un lenguaje no cumple el lema del bombeo, ENTONCES no es infinito y regular.
Como lo anterior es una implicancia, no podemos decir que si un lenguaje cumple el lema del bombeo es regular.
Por lo tanto, la forma de usarlo es siempre para demostrar que un lenguaje NO es regular, NUNCA AL REVES!




Forma Normal de Greibach (1)
Definición:
􀁺 Una GLC se dice que está en Forma Normal de
Greibach (FNG) si todas sus producciones son de la
forma:
A → aα, donde A ∈ N, a ∈ T, α ∈ N*
􀁺 Excepcionalmente se permite la producción S → ε
cuando ε, ∈ L(G).
􀁺 ¿Hasta qué profundidad deberíamos explorar el árbol
de expansión para decidir si una cadena w de longitud n
es generada o no por una gramática en FNC/FNG?



Eliminación de recursividad a izquierdas (1):

􀁺 Dada una GLC G, se dice que una producción es
recursiva a izquierdas si tiene la forma:
A → Aβ, donde A ∈ N, β ∈ (N∪T)*
􀁺 Para pasar una GLC G a FNG necesitaremos que esté
limpia y que no contenga recursividad a izquierdas.



Eliminación de recursividad a izquierdas (2):

􀁺 Algoritmo:
1. Para cada símbolo no terminal A con recursividad a
izquierdas tendremos:
A → Aα1 ... Aαr β1 ... βs
2. Para cada símbolo de este tipo, crear un nuevo no
terminal Bi y sustituir el anterior conjunto de
producciones por el siguiente:
A → β1 ... βs β1Bi ... βsBi
Bi → α1 ... αr α1Bi ... αrBi

0 Comments:

Post a Comment

<< Home