Clase 19 - AFNoDet Resumido

Vista previa del material en texto

ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
Son AF cuya función de transición tiene como 
rango la potencia del conjunto de estados: 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Q 2
Q
q1
q2
q3
q4
q2
q1 q2
q1 q2 q4
q1 q2 q3 q4
. . . . . . . . .
. . . .
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
Para el dominio de la función de 
transición, se distinguen 3 casos: 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Q
q1
q2
q3
q4

a
b
c
Caso 1: AFND
x =
(q1 , a)
. . . .
. . . .
(q4 , b)
(q2 , c)
Que además admite más de un estado inicial.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Q
q1
q2
q3
q4
{} 
a
b
c
Caso 2: AF-
x =
(q1 , a)
. . . .
. . . .
(q4 , b)
(q3 , )

En este caso se admite un 
solo estado inicial.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Q
q1
q2
q3
q4
* 
a
ba
cbab
Caso 2: AF-Lazy
x =
(q1 , a)
. . . .
. . . .
(q4 , ba)
(q3 , )

En este caso se admite un 
solo estado inicial.
. . . .
. . .
. . .
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATAS FINITOS NO DETERMINISTAS:
EJEMPLOS DE AF No-Deterministas y sus ER:
ER = a.(a+b)*.b
AFND2
a,b
1 20 a b
ER = c.a*.b*+(c.b)*.c.a.c.b*
AFND1
a
20 c b
4 c
b
1b c3
5 a
c
ER = c.a*.b*+(c.b)*.c.a.c.b*
AF-1
a
20 c 
4 c
b
b
c3
5
ac
6
ER = c.a*.b*+(c.b)*.c.a.c.b*
AF-Lazy1
a
2
0
c

3
cac
b
cb
1
6
1
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE EQUIVALENCIA ENTRE AFND Y AF- :
AFND3
a
5
1
a
b
2
b
b
3
b
a
4
a
a
7
a,b
a
a b
b
b
AF-2
a1
b
2
b
b
8
b
a
4
a
a
b
6
7
a,b
a
b

0



3
6
5

 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
EQUIVALENCIA ENTRE LOS 3 MODELOS:
ING. JORGE BUABUD
LENGUAJES REGULARES Y 
AUTÓMATAS FINITOS
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE EQUIVALENCIA ENTRE AF-Lazy y AF-:
AF-Lazy2
cba
c2
ca
ca
a
3
10


AF-3
c
2
c
c
a
0

a
b
c
a
b
a
c
5
7
8
6
4
9
3
1
 

EQUIVALENCIA ENTRE LOS 3 MODELOS:
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
ASOCIACIÓN ENTRE AF Y GR:
Existe una equivalencia entre los AF =  Q ,  , q0 , F, f  descriptos 
hasta ahora, ya sean Deterministas o No-deterministas con un 
solo estado inicial, con las GR =  N , T , P, S .
ALGORITMO AFGR
N=Q , T= , S=q0
f(q,w)=p  q→wp 
P
qF  q→
ALGORITMO GRAF
Q=N{E} , =T , q0=S , F={E}
N1→wN2  f(N1,w)=N2
f 
N1→w  f(N1,w)=E
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
Donde w  T*
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE TRANSFORMACIÓN AF → GR:
Para mayor claridad se han cambiado los nombres de los estados 
por letras mayúsculas, acorde a la nomenclatura de No-terminal:
AFND2  GR2
N={S, A, B} , T={a, b}
P={ S→aA , A→aA|bA|bB , B→ }
AF-2  GR1
N={S, A, B, C, D, E, F, G,H}
T={a, b}
P={ S→A|D|F , A→aA|bB , 
B→aC|bE|aD , C→aC|H , 
D→bA|bE , E→bE|H , H→ 
F→aG|bF|H , G→B|aG|bG} 
AF-Lazy1  GR3
N={S, A, B, C} , T={a, b, c}
P={ S→cA|C , A→aA|B , 
B→bB| , C→cacB|cbC }
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ASOCIACIÓN ENTRE AF Y GR:
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE TRANSFORMACIÓN GR → AF:
aa
FS
aba

Aba
B

bb , 
a
AF-Lazy3
GR4={S, A, B} , {a, b} , P , S 
S → abaB | bb |  | A
P A → baS | a
B → aaA | 
F
B
a
a
AC
a
b
b
S
a
b
b
GR5={S, A, B, C} , {a, b} , P , S 
S → aB
A → bC | bA | b
B → aC | bB | a
C → aA
P
AFND4
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ASOCIACIÓN ENTRE AF Y GR:
ING. JORGE BUABUD
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 75
a, b, c
a, b, c
a, b, c
AF-Lazy1
a
3
1
c

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}   
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
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
74
aba

5ba
6

bb , 
a
AF-Lazy3AFD7
2
a, b, c
a, b, c
a, b, c


1 3
AF-Lazy5
AF-
Lazy5
a 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        
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
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-4
b
1
4
32
6
5
b
b,a
a
b
a
a b
a
a
b
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}
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
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-6AFD7
2 31
a, 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-5b
1
2
3
b
a
4b,a
a
b
a
AFD2


Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
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-7
b
0
4
3b
b,a
a
b
a
a
ba
a
b
AFD4
1



6
5
2
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
OPERACIONES CON AUTÓMATAS FINITOS:
EJEMPLO DE COMPLEMENTO:
ER = λ+b.b*.a+(a+b.b*.a.a).(a+b)*+b.b*.a.b.(a+b.b.b)*.b.(b+(a+b.a).(a+b)*)
AFD14
b
2
6
5
1
4
3b
b,a
a
b
a
a b
a
a
b
AFD4
AFD14 a b
→*1 4 2
2 3 2
*3 4 6
*4 4 4
5 4 3
6 6 5
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
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 6
a, b, c c
4
a, b a
7a, b, c
b, c
AFD7
2 31
a, b, c
a, b, c
a, b, c
AFD15 a b c
→A={1,4} B B B
B={2,5} D D C
*C={3,6} E F F
D={3,5} B B E
E={2,6} C G G
F={2,7} G G G
G={3,7} F F F
Aplicando el 
mecanismo de 
minimización se 
determina que los 
nuevos estados F y G 
son equivalentes. 
Con lo que el AFD15 
mínimo queda:
AFD15
Mínimo
A B
D
F
C
E
a, b, c
c
c
a, b a a, b, c
b, c
b, c
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos.