lenguajes regulares y autómatas finitos - clase 9
DESCRIPTION
Autómatas Finitos No Deterministas. Pasaje de GR a AF y de AF a GR. Operaciones entre AF.TRANSCRIPT
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
Son aquellos AF cuyas relaciones de transición pueden tener varias reacciones para un mismo estímulo.Podemos distinguir 3 modelos que tienen esta característica, los mismos difieren en el dominio de la relación de transición y son totalmente equivalentes:
1) AFND = Q, , Q0 , F, f con f: Q x 2Q
donde Q0Q es un subconjunto de estados iniciales.
2) AF- = Q, , q0 , F, f con f: Q x {} 2Q
donde la entrada puede ser vacía o sea transicionar sin leer.
3) AF-Lazy = Q, , q0 , F, f con f: Q x * 2Q
donde la entrada puede ser una palabra cualquiera sobre .
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLOS DE AUTÓMATAS NO DETERMINISTAS:
ER = a.(a+b)*.b
AFND2
a,b
2 31 a b
ER = c.a*.b*+(c.b)*.c.a.c.b*
AFND1
a31 c b
5 c
b
2bc4
6 ac
ER = c.a*.b*+(c.b)*.c.a.c.b*
AF-1
a31 c
5c
b
bc4
6ac
7
ER = c.a*.b*+(c.b)*.c.a.c.b*
AF-Lazy1
a3
1c
4
cac
b
cb
2
7
2
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
REPRESENTACIÓN MATRICIAL:
En esta formade representarla relación detransición, sedebe tener en cuenta que unelemento del
rango es en general un subconjunto.Por eso se los coloca entre llaves y cuando es vacío se usa el símbolo .
AF-1 a b c
1 {2} {5}
2 {2} {3}
* 3 {3}
4 {4}
5 {4,6}
6 {7}
7 {3}
AF-Lazy1 a b c cb cac
1 {2} {4}
2 {2} {3}
*3 {3}
4 {4} {3}
AFND2 a b
1 {2}
2 {2} {2,3}
* 3
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EQUIVALENCIA ENTRE LOS 3 MODELOS:
Como dijimos anteriormente, los tres modelos no deterministas
son equivalentes y se puede pasar de uno a otro fácilmente.
Podemos afirmar que el formato del AF-Lazy incluye al AF-.
Por otro lado el AFND puede considerarse como un caso
particular del AF-, donde los distintos estados iniciales que se
permite, pueden confluir en uno solo mediante transiciones .
De igual modo, cuando trabajamos con AF- se puede unificar los
estados finales con transiciones .
Las transiciones permiten en general disminuir la cantidad de
transiciones del AF y las transiciones con “palabras” contribuyen
a la reducción de la cantidad de estados del AF.
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLO DE EQUIVALENCIA ENTRE AFND Y AF- :
AFND3
a
5
1
a
b2
b
b
3b
a
4
a
a
7
a,b
a
a b
b
b
AF-2
a1b
2
b
b
8
b
a
4
a
a
b
67
a,b
a
b
0
3
6
5
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLO DE EQUIVALENCIA ENTRE AFND Y AF-Lazy:
AFND4 AF-Lazy2
a
6b
c2
b3
b
c
4
a
7a
a c
b
1
5
c
cab, bb, cacbc4
ca
caa
aa
3
10
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
ASOCIACIÓN ENTRE AF Y GR:
Existe una analogía entre los AF = Q , , q0 , F, f descriptos hasta
ahora, ya sean deterministas o no, con las GR = N , T , P, S .
ALGORITMO AFGR
N=Q , T= , S=q0
f(q,w)=p qwp
P f(q,w)F qw
q0F q0
ALGORITMO GRAF
Q=N{E} , =T , q0=S , F={E}
N1wN2 f(N1,w)=N2
f N1w f(N1,w)=E
S f(S,)=E
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLOS DE TRANSFORMACIÓN DE AF A GR:
Para mayor claridad se ha realizado algunos cambios en los
nombres de los estados y se ha eliminado no-terminales inútiles:
AFND2 GR
N={S, A} , T={a, b}
P={ SaA , AaA|bA|b }
AF-2 GR
N={S, A, B, C, D, E, F, G}
T={a, b}
P={ SA|D|F , AaA|bB ,
BaC|bE|aD , CaC| ,
DbA|bE , EbE| ,
FaG|bF| , GB|aG|bG}
AF-Lazy1 GR
N={S, A, B, C} , T={a, b, c}
P={ ScA|C , AaA|B| ,
BbB|b , CcacB|cbC|cac }
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLOS DE TRANSFORMACIÓN DE GR A AF:
aa
FSaba
Aba
B
bb ,
a
AF-Lazy3GR={S, A, B} , {a, b} , P , S
S abaB | bb | | A
P A baS | a
B aaA |
F
Ba
a
ACa
b
b
Sa
b
b
GR={S, A, B, C} , {a, b} , P , S
S aBA bC | bA | bB aC | bB | aC aA
P
AFND5
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
UNIÓN:
La Unión de dos AF, ya sean deterministas o no, en general da como
resultado un AF-Lazy tal que reconoce la unión de los lenguajes que
aceptan los autómatas operandos.
El mecanismo consiste en crear un estado inicial nuevo y definir
transiciones- desde éste hacia los estados iniciales de los AF de partida.
AF1
AF2
AF3
AF3 = AF1AF2
L(AF3)=L(AF1)L(AF2)
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
EJEMPLO DE UNIÓN:ER = ((a+b+c).(a+b+c))*+ c.a*.b*+(c.b)*.c.a.c.b*
OPERACIONES CON AUTÓMATAS FINITOS:
AF-Lazy4
AFD7
6 75a, b, c
a, b, c
a, b, c
AF-Lazy1a
3
1c
4
cac
b
cb
2
0
AF-Lazy4 a b c cb cac
0 {1,5}
1 {2} {4}
2 {2} {3}
*3 {3}
4 {4} {3}
*5 {6} {6} {6}
6 {7} {7} {7}
*7 {6} {6} {6}
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
CONCATENACIÓN:
La Concatenación o Producto de dos AF, ya sean deterministas o no, en
general da como resultado un AF-Lazy tal que reconoce el producto de
los lenguajes que aceptan los autómatas operandos.
El mecanismo consiste en colocar transiciones- desde todos los finales
del primero al inicial del segundo. Estos estados pasan a ser comunes.
AF3 = AF1.AF2 , L(AF3)=L(AF1).L(AF2)
AF1 AF2AF3
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE CONCATENACIÓN:ER = ((a+b+c).(a+b+c))*.(a.b.a.a.a.b.a+b.a)*.(a.b.a.a.a.a+a.b.a+b.b+a+)
aa
74aba
5ba
6
bb ,
a
AF-Lazy3AFD7
2a, b, c
a, b, c
a, b, c
1 3
AF-Lazy5
AF-
Lazy5a b c aa ba bb aba
1 {2} {2} {2} {4}
2 {3} {3} {3}
3 {2} {2} {2} {4}
4 {7} {6} {5,7}
a b c aa ba bb aba
5 {7} {4}
6 {5} {7}
*7
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
ESTRELLA DE KLEENE:
La operación Estrella de Kleene de un AF, ya sea determinista o no, en
general da como resultado un AF-Lazy tal que reconoce la estrella de
Kleene del lenguaje que acepta el autómata base.
El mecanismo consiste en colocar transiciones- desde todos los finales al
inicial y crear un nuevo inicial/final con una transición- al inicial viejo.
AF3 = AF1*
L(AF3)=L(AF1)*
AF1
AF3
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE ESTRELLA DE KLEENE:
ER = (b.b*.(a.b.(a+b.b.b)*.(a+b.b.b+b)+a.b+b)+b)*
AF-3
b
1
4
32
6
5
b
b,a
a
ba
a b
a
ab
AFD4
0
AF-3 a b
0 {1}
1 {4} {2}
*2 {3} {2} {1}
3 {4} {6}
4 {4} {4}
*5 {4} {3} {1}
*6 {6} {5} {1}
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
ESTRELLA POSITIVA:
La operación Estrella Positiva de un AF, ya sea determinista o no, en
general da como resultado un AF-Lazy tal que reconoce la estrella
positiva del lenguaje que acepta el autómata base.
El mecanismo consiste en colocar transiciones- desde todos los finales al
inicial.
AF3 = AF1+
L(AF3)=L(AF1)+
AF1AF3
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE ESTRELLA POSITIVA:
ER = X.X*
X = a*.b.b*.
(a.b.b*+a+b)
+ a*.b
ER = ((a+b+c).(a+b+c))*
AF-5AFD7
2 31a, b, c
a, b, c
a, b, c
AF-4 a b
1 {1} {2}
*2 {3} {2} {1}
*3 {4} {3} {1}
4 {4} {4}
AF-5 a b c
*1 {2} {2} {2}
2 {3} {3} {3}
*3 {2} {2} {2} {1}
AF-4b
1
2
3
ba
4b,a
a
ba
AFD2
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
INVERSA:
La Inversa de un AF, ya sea determinista o no, en general da como
resultado un AF-Lazy tal que reconoce la inversa del lenguaje que
acepta el autómata base.
El mecanismo consiste en invertir todas las transiciones del AF, luego
crear un nuevo estado inicial con transiciones- hacia todos los estados
finales, éstos pierden tal condición y el estado inicial viejo pasa a ser el
único final.
AF1AF3
AF3 = AF1-1
L(AF3)=L(AF1)-1
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE INVERSA:
ER = (b+b.a+(a+b.b.b+b).(a+b.b.b)*.b.a).b.b*+b
AF-6 a b
0 {2,5,6}
*1
2 {2,1}
3 {2} {5}
4 {1,3,
4,5}{4}
5 {6}
6 {6} {3}
AF-6
b
0
4
3b
b,a
a
ba
a
ba
a
b
AFD4
1
6
5
2
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
COMPLEMENTO:
Para obtener el Complemento de un AF, o sea el AF que reconozca el
complemento del lenguaje que acepta el autómata base, se requiere que
el modelo sea DETERMINISTA y completo.
El mecanismo consiste en convertir en finales los estados no-finales y
viceversa.
AF3 = AF1
L(AF3)= L(AF1)
AF1 = Q1 , , q10 , F1 , f1
AF3 = Q3 , , q30 , F3 , f3
Q3=Q1 , q30=q10 , f3=f1
F3=Q1-F1
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE COMPLEMENTO:
ER = b.b*.(a.(b.b.b)*.((a+b.a*.b.a).(a+b).(a+b)*+b.a.a+b.b.b+a)+a)+a.(a+b)*+
AFD14
b
2
6
5
1
4
3b
b,a
a
ba
a b
a
ab
AFD4
AFD14 a b
*1 4 2
2 3 2
*3 4 6
*4 4 4
5 4 3
6 6 5
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
INTERSECCIÓN:
Para obtener la Intersección de dos AF, o sea el AF que reconozca la
intersección de los lenguajes que aceptan los autómatas operandos, se
requiere que los modelos sean DETERMINISTAS y completos.
El mecanismo se representa formalmente a continuación:
AF1 = Q1 , , q10 , F1 , f1
AF2 = Q2 , , q20 , F2 , f2
AF3 = Q3 , , q30 , F3 , f3
Q3Q1xQ2 , q30=[q10 , q20] , F3F1xF2
f3([q1,q2],x)=[f1(q1,x) , f2(q2,x)]
AF3 = AF1AF2
L(AF3)=L(AF1)L(AF2)
ING. JORGE BUABUD
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
U.T.N. – F.R.T.
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE INTERSECCIÓN:
ER = (a+b+c).((a+b).(a+b))*.(a.c.a+b.c.a+c).(a.a)*
AFD5
5 6a, b, c c4
a, b a
7a, b, cb, c
AFD7
2 31a, b, c
a, b, c
a, b, c
AFD15 a b c
0={1,4} 1 1 1
1={2,5} 3 3 2
*2={3,6} 4 5 5
3={3,5} 1 1 4
4={2,6} 2 6 6
5={2,7} 6 6 6
6={3,7} 5 5 5
Aplicando el
mecanismo de
minimización se
determina que los
nuevos estados 5 y 6
son equivalentes.
Con lo que el AFD15
mínimo queda:
AFD15
0 1
3
5
2
4
a, b, c
c
c
a, b a a, b, c
b, c
b, c