Clase 21 - Resumido - AFLambda de una ER - Propiedades de LR

Vista previa del material en texto

U.T.N. – F.R.T. 
S. y S. de los L.
OBTENCIÓN DEL AF- A PARTIR DE UNA ER:
ING. JORGE BUABUD
Las siguientes plantillas de AF-, conocidas como CONSTRUCCIONES 
DE THOMPSON, corresponden a ER sencillas, donde x  y  : 
x
x
x+y
y
x

 

x.y
x y
x*


x 



Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L.
OBTENCIÓN DEL AF- A PARTIR DE UNA ER:
ING. JORGE BUABUD
MÉTODO DE THOMPSON: A partir de una ER, con alfabeto
base , se puede construir el AF- que acepta el lenguaje asociado
con dicha expresión, mediante las siguientes pautas:
1) Se construye un AF- correspondiente a cada símbolo de  y 
también para  si fuera necesario.
2) Se procede a realizar las operaciones entre estos AF-, de 
acuerdo a la ER de partida.
3) Se recomienda unificar los estados finales en cada paso.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE OBTENCIÓN DEL AF DE UNA ER:
ING. JORGE BUABUD
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ER = a.(a+b.a*.c)*.c+b.b.a
AF-8
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE OBTENCIÓN DEL AF DE UNA ER:
ING. JORGE BUABUD
ER = a.(a+b.a*.c)*.c+b.b.a
AF-8 Simplificado
a
1
a
2
c
b
14
c
a
4
b b
7
a
0

 3
65



1210 11
8 9
13




Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
Derivada de una ER:
Con el objetivo de plantear otro método para llegar al AF a 
partir de una ER, vamos a definir el concepto de derivada.
La derivada de una expresión regular “E” respecto a un símbolo 
“x” perteneciente a un alfabeto “”, se define como:
Dx(E) = {w / x.w  E}
Es decir del conjunto de palabras “w” que están representadas por 
“E”, se selecciona aquellas que comienzan por el símbolo “x” 
respecto al que se deriva y la derivada será el conjunto de los restos 
de esas palabras sin el prefijo “x”.
EQUIVALENCIA ENTRE ER, GR Y AF:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L. 
Obtención de la GR que genera el lenguaje de una ER:
Dada una ER E0 y el conjunto D de todas las ER Ei distintas que se 
obtienen por derivación compuesta con respecto a todos los símbolos x 
de , el alfabeto base de E0 ; los componentes de la gramática G que 
genera el lenguaje definido por E0 son:
N = {E0}  D , T =  , S = E0
ING. JORGE BUABUD
P = 
Si Dx(E1)=E2 , E2  , E2 , crear la regla E1 → x E2
Si Dx(E1) , crear una regla E1 → x
Si E0 , crear una regla E0 → 
Si Dx(E1)= , no crear ninguna regla 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
EQUIVALENCIA ENTRE ER, GR Y AF:
U.T.N. – F.R.T. 
S. y S. de los L. 
Ejemplo de obtención del AF a partir de la GR asociada a una ER:
Partamos de la siguiente ER: E0 = a*.b.(a+b)*.b
Da(E0) = E0
Db(E0) = (a+b)*.b = E1
Da(E1) = E1
Db(E1) = (a+b)*.b+ = E2
Da(E2) = E1
Db(E2) = E2
ING. JORGE BUABUD
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
EQUIVALENCIA ENTRE ER, GR Y AF:
N = {E0 , E1}
T = {a, b} 
S = E0
GR6
Vemos que las derivadas de 
E1 y E2 son equivalentes, 
entonces unificamos con E1 AFND5
U.T.N. – F.R.T. 
S. y S. de los L.
PROPIEDADES DE LOS LENGUAJES REGULARES:
ING. JORGE BUABUD
Con el objetivo de responder a la pregunta ¿ es L un lenguaje regular ? 
podemos tener en cuenta:
✓ Las cláusulas de definición de un LR. Una de esas cláusulas 
decía que todo lenguaje finito es un LR. 
✓ Todo LR tiene asociado un AF que lo acepta y una GR que lo 
genera.
✓ Siempre es posible obtener un AF al realizar las operaciones: 
Unión, Concatenación, Estrella de Kleene, Estrella positiva,
Inversa, Complemento e Intersección; con Autómatas Finitos. 
Es decir que los LR son cerrados con respecto esas operaciones.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L.
PROPIEDADES DE LOS LENGUAJES REGULARES:
ING. JORGE BUABUD
El problema se presenta cuando tenemos un lenguaje infinito y no 
encontramos fácilmente una ER o GR o AF que lo describa. 
En este caso podemos recurrir a la siguiente propiedad que solo tienen los 
lenguajes regulares y cuyo enunciado se conoce como “Lema de bombeo” 
(Pumping Lemma):
Supongamos que L es un lenguaje regular, aceptado por un AFD 
con “n” estados. Entonces, si L contiene una palabra de largo 
mayor o igual que “n”, L es necesariamente infinito. Más aún: 
para toda wL, |w|  n, existen x, y, z  * tales que w = xyz, 
|y| > 0 , |xy|  n y, para todo i0 , xyiz  L.
Se dice que la subsecuencia “y” se puede “bombear” (borrar o 
repetir “i” veces) y la palabra “w” sigue perteneciendo a L.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L.
PROPIEDADES DE LOS LENGUAJES REGULARES:
ING. JORGE BUABUD
Este enunciado se justifica con el hecho de que en un AFD se deben realizar |w| 
transiciones para aceptar la secuencia “w”. Y esto implica que si |w|  n, 
entonces necesariamente se debe transicionar por algún estado más de una 
vez. O sea que hay circuitos que comienzan y terminan en un mismo estado:
AFD
q1 qi
qj=qk
qj+1
qk+1 qn
La secuencia “x” 
recorre desde q1 hasta 
qk , la cadena “y” 
recorre el circuito 
sobre qk y “z” 
termina el trayecto 
hasta el estado final 
qn.
AFD
q1 qi
qj=qk
qj+1
qk+1 qnq1 qi
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L.
PROPIEDADES DE LOS LENGUAJES REGULARES:
ING. JORGE BUABUD
Ejemplo de Lema de Bombeo: 
¿Es el lenguaje L = { ak bk / k=1,2,3,.... } un LR?
Supongamos que L es regular y sea “n” la cantidad de estados del AFD 
que lo reconoce. Por el Lema de Bombeo, si tomamos w=anbn, deben 
existir x, y, z  {a, b}*, tales que w=xyz, |y| > 0 y xyiz  L para todo 
i=0,1,2,3....; en particular debe cumplirse que xy2z  L. Pero:
✓ si “y” está formado solamente por “a”, xy2z tiene más “a” que “b”, 
por lo que xy2z  L
✓ análogamente, si “y” está formado solamente por “b”, xy2z tiene 
más “b” que “a”, por lo que xy2z  L
✓ finalmente, si “y” está formado por “a” y “b”, entonces y=ajbk con 
j,k > 0, por lo que xy2z = xajbkajbkz = anbkajbn, que no pertenece a 
L ya que tiene “b” que preceden a las “a”.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos.