Teorema de Nerode. Minimización de AFDs
9
Teorema de Nerode. Minimización de AFDs tos previos: Partición de un conjunto. Relación sobre un conjunto A. Relación de equivalencia. Clase de equivalencia. El conjunto de las clases de equiv. de A es una par Conjunto cociente. Indice de una relación. R (sobre A) es más fina que Q si x,y A (x R y x Q y) es congruencia sobre M si x R y u,v M (uxv R uyv). es cong. a derechas sobre M si x R y v M (xv R yv). es cong. a izquierdas sobre M si x R y u,v M (ux R uy)
description
Teorema de Nerode. Minimización de AFDs. Conceptos previos: -Partición de un conjunto. -Relación sobre un conjunto A . -Relación de equivalencia. -Clase de equivalencia. -El conjunto de las clases de equiv. de A es una partición. -Conjunto cociente. -Indice de una relación. - PowerPoint PPT Presentation
Transcript of Teorema de Nerode. Minimización de AFDs
Teorema de Nerode. Minimización de AFDs
Conceptos previos:-Partición de un conjunto.-Relación sobre un conjunto A.-Relación de equivalencia.-Clase de equivalencia.-El conjunto de las clases de equiv. de A es una partición. -Conjunto cociente.-Indice de una relación.-R (sobre A) es más fina que Q si
x,y A (x R y x Q y)
R es congruencia sobre M si x R y u,v M (uxv R uyv).R es cong. a derechas sobre M si x R y v M (xv R yv).R es cong. a izquierdas sobre M si x R y u,v M (ux R uy).
Relación de equivalencia de los buenos finales:-Dado L *; x, y * ( x RL y x -1 L = y -1 L ).-De manera equivalente
x, y * ( x RL y z *( xz L yz L )).
RL es una congruencia a derechas: Dem.- Si x RL y, z * (xz) -1 L = z -1 (x -1 L) = z -1 (y -1 L) =
= (yz) -1 L xz RL yz
Ejercicio: Sea A = (Q, , , q0, F) un AFD completo y accesible.Sea RA : x, y * ( x RA y (q0, x) = (q0, y) ).
- RA es una RBE de índice finito.- RA es una congruencia a derechas.
Dado L *; son equivalentes:1.- L es regular.2.- L es unión de algunas clases de equivalencia de una congruencia a derechas de índice finito.3.- RL es de índice finito.
Teorema de Nerode
Demostración:(1 2) L es regular L = L(A) con A = (Q, , , q0, F).La relación es RA : x, y * ( x RA y (q0, x) = (q0, y) ).
- es una RBE de índice finito.- es una congruencia a derechas.- cada clase representa un estado de Q.- L es unión de aquellas clases de RA que corresponden con eltos de F.
(2 3) Sea E congruencia a derechas de índice finito.x E y z * , xzEyz z * (xz L yz L) x RL y.Si E es de índice finito y es más fina que RL, esta también.
A = (Q, , , q0, F)
{[u] RL : u *}
función de transición([u] RL
,a) = [ua] RL a
q0 = [] RL
{[u] RL : u L}
(3 1) Sea RL de índice finito,
-Se cumple que ([] RL ,x) = [x] RL
x *. Entonces
L(A) = {x * : ([] RL ,x) F }= {x * : [x] RL
F }=
{x * : x L } = L ( L= L(A) L es Regular ).
Minimización de Autómatas Finitos
-Un autómata A = (Q, , , q0, F) es accesible si q Q x * : (q0, x) = q.-R. de indistiguibilidad: Si A es completo y accesible se define q,q’ Q (q q’ x * ((q, x) F (q, y) F )).
Dado A = (Q, , , q0, F) , el autómata cociente A/ = (Q’, , ’, q’0, F’) conQ’ = Q/ = {[q] : q Q }; q’0 = [q0]
F’ = F/ = {[q] : q F };’([q] , a) = [(q, a)]
es el autómata mínimo que acepta L(A).
El problema de minimizar un AFD se reduce a computar
R. de k-indistiguibilidad: Si A es completo y accesible, q,q’ Q (q k q’ x *, |x| k ((q, x) F (q, y) F )).• k 0 p k + 1 q p k q .• k 0 p q p k q .• k 0 p k + 1 q p k q a ((p, a) k (q, a)).• p 0 q (p F q F) (p Q - F q Q - F)
Algoritmo de minimización:(1) 0 = {Q - F , F}(2) Obtener k + 1 a partir de k : B(p, k + 1) = B(q, k + 1) B(p, k ) = B(q, k ) a (B((p, a), k ) = B((q, a), k ))(3) Repetir (2) hasta encontrar m : m + 1 = m .
1
0 1
1
1 1
10
0
0
0
0
1
1 3
2
5
4 76
a
1
3
2
5
4
6
a
a
a
a
a
b
bb
b
bb
0
a
1
3
2
5
4
6
a
a
a
a
a
b
bb
b
bb
