Página 58 - Coordinación de Servicios de Información

·I~/·: I-l![ff~!:>;;:" ~:}. . -;-- ~. i
~~:'t.r ,. i"t'...·; '.~. ~. '-':
!t r.N :;."i" ~(::'.t~"-"~' ...- ',..
...... ;...;..';.. :7 4:' ",""'_ .~ ;'11." • • ,,,,
~ ~.~~1>.x . ',. " . ". . , ':., -- ~ .
... '" .. ..,., , .... -.
S, [ d ] < e > ( b ) S" S22I
[ f] < h > ( b ) S" S,,,
S" < c > a [ d ] S", S,
< e > g [f] S", S,
< h > a [f] S", S,
S,,, (b) <c > ( b) S" S22I
S", a g (b) S", S,,,
g a ( b ) S", S'2I
Podemos observar que la tabla de estados de la máquina M, se ha dividido en las siguientes
clases de equivalencia: ( d,f ), ( c,e,h ), ( b ) & ( a,g). Se pueden eliminar los estados
redundantes en cada clase de equivalencia, para producir la máquina mínima de estados M '. El
diagrama de estados reducido se presenta a continuación:
o
o
I / I
df
o
Figura No. 7: Diagrama reducido de estados.
_Método dp 1.. carta de implican tes:
Otro proceso de reducción de estados para las tablas de estado, se basa en las clases de
equi valencia de dichos estados en la tabla. Hay ocasiones en que un par de estados no tienen los
mismos estados siguientes, pero pasan a estados subsecuentes que pertenecen a la misma clase
de equivalencia. Esto implica que si un par de estados c & d, se hallan en t+ 1, Y son
equivalentes, sus estados anteriores a & b, también deben ser equivalentes; porque tienen los
mismos estados siguientes. Cuando esta relación existe se dice que ( a,b ) implica ( c,d ).
La verificación de cada par de estados de equivalencia en una tabla con un número grande de
estados, se puede simplificar utilizando una tabla de implicación. Esta consta de una matriz
página 2-16