Siguiente: Autómatas finitos Un nivel arriba: Máquinas secuenciales Anterior: Máquinas de Moore

Equivalencia e indistinguibilidad

Sea $M=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$ una máquina, ya sea de Mealy o de Moore. Extendemos la función de transición $\mbox{\it tran\/}:Q\times \mbox{\it Ent\/}\rightarrow Q$ a una función $\mbox{\it tran\/}^*:Q\times \mbox{\it Ent\/}^*\rightarrow Q$, haciendo, para cada estado $q\in Q$:

$$\begin{eqnarray*}\mbox{\it tran\/}^*(q,\mbox{\it nil\/}) &=& q,\\ \forall \sig... ...sigma s) &=& \mbox{\it tran\/}(\mbox{\it tran\/}^*(q,\sigma),s) \end{eqnarray*}$$

Así pues, para cada palabra $\sigma$, $\mbox{\it tran\/}^*(q,\sigma)$ es el estado al que se llega cuando, a partir del estado q, se va aplicando, uno a uno, cada uno de los símbolos de $\sigma$, de izquierda a derecha. De manera similar se puede extender la función de respuesta a todo el diccionario $\mbox{\it Ent\/}^*$. Si M es una máquina de Mealy, definimos $\mbox{\it res\/}^*:Q\times \mbox{\it Ent\/}^*\rightarrow \mbox{\it Sal\/}^*$, haciendo, para cada estado $q\in Q$ y para cada palabra $\sigma \in \mbox{\it Ent\/}^*$, $\mbox{\it res\/}^*(q,\sigma)=\tau\in\mbox{\it Sal\/}^*$ donde,

$$\begin{eqnarray*}\sigma =\mbox{\it nil\/}&\Rightarrow& \tau=\mbox{\it nil\/},\\ ... ...{k-1},s_k) & q_k&=&\mbox{\it tran\/}(q_{k-1},s_k) \end{array} \end{eqnarray*}$$

en otras palabras, se tiene

$$\begin{eqnarray*}\mbox{\it res\/}^*(q,\mbox{\it nil\/}) &=& \mbox{\it nil\/},\\ ... .../}^*(q,\sigma)\mbox{\it res\/}(\mbox{\it tran\/}^*(q,\sigma),s) \end{eqnarray*}$$

Si M es una máquina de Moore, la función de respuesta $\mbox{\it res\/}^*:Q\times \mbox{\it Ent\/}^*\rightarrow \mbox{\it Sal\/}^*$ depende únicamente del estado visitado: para cada estado $q\in Q$

$$\begin{eqnarray*}\mbox{\it res\/}^*(q,\mbox{\it nil\/}) &=& \mbox{\it nil\/},\\ ... ...\/}^*(q,\sigma)\mbox{\it res\/}(\mbox{\it trans\/}^*(q,\sigma)) \end{eqnarray*}$$

En cualquier caso, sea en máquinas de Mealy o de Moore, la función $\mbox{\it trad\/}:\sigma\mapsto \mbox{\it res\/}^*(q_0,\sigma)$, donde q₀ es el estado inicial, es la función de traducción que realiza la máquina. Por las semánticas procedimentales introducidas, se tiene que $\forall \sigma$: $\mbox{\rm long}(\mbox{\it trad\/}(\sigma))=\mbox{\rm long}(\sigma)$.


Dos máquinas M y N se dicen ser equivalentes, $M\equiv N$, si $\mbox{\it trad\/}_M=\mbox{\it trad\/}_N$. En otras palabras, dos máquinas son equivalentes si ambas traducen de idéntica manera a cualquier palabra de entrada. Ya que las máquinas de Moore son casos particulares de las máquinas de Mealy, se tiene que toda máquina de Moore es equivalente a una de Mealy. Veamos que el recíproco también se cumple:

Proposición 1.1   Toda máquina de Mealy es equivalente a una de Moore: Para cada máquina de Mealy $\mbox{\it MMe\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$ existe una máquina de Moore $\mbox{\it MMo\/}=(Q',\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/}',\mbox{\it res\/}',q_0')$ tal que $\mbox{\it MMe\/}\equiv \mbox{\it MMo\/}$.

En efecto, dada una máquina de Mealy $\mbox{\it MMe\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$, realicemos la siguiente construcción:

estados:

sea $Q'=Q\times\mbox{\it Sal\/}\cup \{(q_0,\mbox{\it nil\/})\}$. Se ``desdobla'' cada estado ''viejo'' $q\in Q$ en $\mbox{\rm card}(\mbox{\it Sal\/})$ estados ``nuevos'' de la forma (q,t), $t\in\mbox{\it Sal\/}$;

transición:

sea $\mbox{\it tran\/}':((q,t),e)\mapsto (\mbox{\it tran\/}(t,e),\mbox{\it res\/}(t,e))$, donde tran y res son las funciones de transición y de respuesta ``viejas'';

respuesta:

sea $\mbox{\it res\/}':(q,t)\mapsto t$; y

estado inicial:

sea $q_0'=(q_0,\mbox{\it nil\/})$.

Se ve directamente que la máquina de Moore construida es equivalente a la de Mealy dada.


Ejemplo Consideremos la máquina de Mealy del ejemplo 2. anterior que ``reconoce a repeticiones finales de un mismo símbolo en $\{0+1\}$''. Ahí, la máquina tiene transición y respuesta,

$$\begin{array}{c@{\ \ \ }c} \begin{array}{\vert\vert r\vert c... ...& n \\ p_1 & n & s \\ \hline\hline \end{array} \end{array}$$

La máquina de Moore equivalente consiste de 7=1+6 estados

$$q_0\mbox{\it nil\/},q_0n,p_0n,p_1n,q_0s,p_0s,p_1s$$

y sus correspondientes transición y respuesta son

$$\begin{array}{c@{\ \ \ }c} \begin{array}{\vert\vert r\vert c... ...0s & s \\ p_1s & s \\ \hline\hline \end{array} \end{array}$$

Observamos aquí que los estados $q_0\mbox{\it nil\/},q_0n,q_0s$ no aparecen en la imagen de la función de transición nueva. Por tanto, los restantes cuatro estados, junto con el inicial, definen una máquina de Moore de 5 estados equivalente a la máquina de Mealy dada.


En lo que resta de esta sección, consideraremos únicamente máquinas de Moore. Sea $\mbox{\it MMo\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$ una máquina de Moore. Se dice que $\mbox{\it MMo\/}$ es una máquina-(n,m,k) si $n=\mbox{\rm card}(Q)$ es el número de estados, $m=\mbox{\rm card}(\mbox{\it Ent\/})$ es el número de símbolos de entrada y $k=\mbox{\rm card}(\mbox{\it Sal\/})$ es el número de símbolos de salida, que son efectivamente asumidos bajo la función de respuesta res. Sea $f_{\mbox{\scriptsize\it MMo}}=\mbox{\it res\/}\circ \mbox{\it tran\/}^*$ la función que, para un estado q y una palabra $\sigma$, da el último símbolo de respuesta cuando se aplica $\sigma$ a partir de q. Diremos que dos estados q₁, q₂ son indistinguibles, $q_1\sim_{\mbox{\scriptsize\it Ind}}q_2$, si para cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$ se tiene $f(q_1,\sigma)=f(q_2,\sigma)$. Intuitivamente, dos estados son indistinguibles si no se los puede distinguir mediante una sucesión de estímulos, pues ambos estados ofrecen mismas respuestas ante mismas entradas. Los estados son distinguibles si para alguna palabra $\sigma$ se tiene $f(q_1,\sigma)\not=f(q_2,\sigma)$, y en tal caso, se dice que $\sigma$ los distingue.

Proposición 1.2   Cualesquiera dos estados distinguibles en una máquina-(n,m,k) lo son mediante una palabra de longitud a lo sumo n-k.

En efecto, para cada $i\geq 0$ sea I_i el conjunto de parejas de estados que no pueden ser distinguidos por palabras de longitud i,

$$I_i=\{(q_1,q_2)\in Q^2\vert\forall \sigma\in\mbox{\it Ent\/}^... ...m long}(\sigma)\leq i\Rightarrow f(q_1,\sigma)=f(q_2,\sigma)\}.$$

I_i es una relación de equivalencia. Sea $\iota_i$ el índice de la relación I_i. Ya que la sucesión de relaciones $\{I_i\}_i$ es decreciente, o sea,

$$\forall (q_1,q_2)\in Q^2: \ \ (q_1,q_2)\in I_i\Rightarrow (q_1,q_2)\in I_{i-1},$$

se tiene que la correspondiente sucesión de índices $\{\iota_i\}_i$ es creciente,

$$\mbox{\rm card}(\mbox{\it Sal\/}')=\iota_0\leq \iota_1\leq \cdots \leq \iota_i\leq \iota_{i+1}\leq\cdots$$ (5)

Naturalmente, $\mathop{\rm Max}_{i\geq 0}\{\iota_i\}\leq \iota_{+\infty}\leq \mbox{\rm card}(Q)$, donde $\iota_{+\infty}$ es el índice de la relación `` $\sim_{\mbox{\scriptsize\it Ind}}$''. Por tanto, necesariamente, $\exists i_0:\ \iota_{i_0}=\iota_{i_0+1}$, y, de hecho, $\forall i\geq i_0: \ I_i=I_{i_0}$. De aquí puede verse que las desigualdades intermedias en la serie de relaciones 3.1 son estrictas, es decir

$$\mbox{\rm card}(\mbox{\it Sal\/}')=\iota_0< \iota_1< \cdots < \iota_{i_0}\leq\mbox{\rm card}(Q),$$

y, en particular, $\mbox{\rm card}(\mbox{\it Sal\/}')+i_0\leq\mbox{\rm card}(Q)$. Por tanto, el número de relaciones distintas de la forma I_i está mayorizado por la desigualdad $i_0\leq \mbox{\rm card}(Q)-\mbox{\rm card}(\mbox{\it Sal\/}')$, quod erat demonstratum.


La proposición anterior proporciona un algoritmo elemental para calcular, de manera exhaustiva, al cociente $Q/\sim_{\mbox{\scriptsize\it Ind}}$:

1.

Sean $\mbox{\it ne\/}=\mbox{\rm card}(\mbox{\it Ent\/})$, $\mbox{\it nq\/}=\mbox{\rm card}(Q)$ y $\mbox{\it ns\/}=\mbox{\rm card}(\mbox{\it Sal\/}')$ las cardinalidades de los conjuntos de símbolos de entrada, estados y símbolos de salida asumidos.

2.

Sea $k=\frac{\textstyle \mbox{\it ne\/}^{\mbox{\scriptsize\it nq}-\mbox{\scriptsize\it ns}+1}-1}{\textstyle \mbox{\it ne\/}-1}$ el número de palabras de longitud a lo más $\mbox{\it nq\/}-\mbox{\it ns\/}$.

3.

Fórmese la matriz $F=(f_{ij})_{1\leq i\leq k,1\leq j\leq\mbox{\scriptsize\it nq}}$ tal que $\forall i,j:\ f_{ij}=f(q_j,\sigma_i)$.

4.

Dos estados son indistinguibles entre sí si los correspondientes vectores columnas en F coinciden.

Ejemplo. Residuos módulo 4: Una máquina que reconoce números binarios congruentes con 2 o con 4, módulo 4, se muestra en la figura (3.4).

  

Figure 3.4: Reconocedor de números binarios congruentes con 2 o 4 módulo 4.

Se tiene $\mbox{\it ne\/}=\mbox{\rm card}(\mbox{\it Ent\/})=2$, $\mbox{\it nq\/}=\mbox{\rm card}(Q)=4$ y $\mbox{\it ns\/}=\mbox{\rm card}(\mbox{\it Sal\/}')=2$, luego k=2^4-2+1-1=7. La tabla para reconocer estados indistinguibles queda:

$$\begin{array}{\vert\vert l\vert c\vert c\vert c\vert c\vert\v... ... 1 & 1 & 1 \\ 11 & 0 & 0 & 0 & 0 \\ \hline\hline \end{array}$$

Por tanto, las parejas $[q_0]=\{q_0,q_2\}$ y $[q_1]=\{q_1,q_3\}$ constan de estados indistinguibles entre sí.



Se ve directamente que la relación `` $\sim_{\mbox{\scriptsize\it Ind}}$'' es de equivalencia en el conjunto de estados Q. Por tanto, el cociente $Q/\sim_{\mbox{\scriptsize\it Ind}}$ es una partición de Q. Más aún, si dos estados son indistinguibles, lo son también los estados a los que transitan bajo cualquier estímulo,

$$q_1\sim_{\mbox{\scriptsize\it Ind}}q_2 \;\Rightarrow\; \foral... ...q_1,e)\sim_{\mbox{\scriptsize\it Ind}}\mbox{\it tran\/}(q_2,e),$$

en otras palabras, la noción de indistinguibilidad es congruente con las transiciones de la máquina $\mbox{\it MMo\/}$.

Observación 1.1   El espacio cociente $Q/\sim_{\mbox{\scriptsize\it Ind}}$ puede ser dotado de una estructura de máquina de Moore.

En efecto, la construcción es la siguiente:

estados:

clases de equivalencia $[q]\in Q/\sim_{\mbox{\scriptsize\it Ind}}$, con $q\in Q$,

transición:

$\mbox{\it tran\/}_{\mbox{\scriptsize\it Ind}}:([q],e)\mapsto [\mbox{\it tran\/}(q,e)]$, o sea, la clase de indistinguibilidad de q transita, bajo e a la clase del estado al que transita q. Esta definición tiene sentido pues la indistinguibilidad es congruente con las transiciones,

respuesta:

$\mbox{\it res\/}_{\mbox{\scriptsize\it Ind}}:[q]\mapsto \mbox{\it res\/}(q)]$, la cual función también está bien definida, y

estado inicial:

$q_{0,\mbox{\scriptsize\it Ind}}=[q_0]$, es decir, el nuevo estado inicial es la clase de equivalencia del estado inicial original. En esta clase están incluidos todos los estados indistinguibles respecto a q₀.

Así por ejemplo, la máquina cociente del último ejemplo es la siguiente:

Observación 1.2   La máquina cociente tiene un número de estados que no excede al de la máquina dada. De hecho, si hubiera una pareja de estados indistinguibles entonces el número de estados de la máquina cociente es estrictamente menor. Además, la máquina cociente es equivalente a la máquina dada.

En efecto, veamos que para todo $\sigma \in \mbox{\it Ent\/}^*$, $\mbox{\it res\/}_{\mbox{\scriptsize\it Ind}}^*(\sigma)=\mbox{\it res\/}^*(\sigma)$. Para $\sigma=\mbox{\it nil\/}$ se tiene

$$\mbox{\it res\/}_{\mbox{\scriptsize\it Ind}}^*(\mbox{\it nil\... ...0])=\mbox{\it res\/}(q_0)=\mbox{\it res\/}^*(\mbox{\it nil\/}).$$

Ahora, para $\sigma \in \mbox{\it Ent\/}^*$ y $e\in\mbox{\it Ent\/}$, al suponer que $\mbox{\it res\/}_{\mbox{\scriptsize\it Ind}}^*(\sigma)=\mbox{\it res\/}^*(\sigma)$, se tiene

$$\begin{eqnarray*}\mbox{\it res\/}_{\mbox{\scriptsize\it Ind}}^*(\sigma e) &=& \m... ...tran\/}^*(q_0,\sigma e)) \\ &=& \mbox{\it res\/}^*(\sigma e) \end{eqnarray*}$$

Siguiente: Autómatas finitos Un nivel arriba: Máquinas secuenciales Anterior: Máquinas de Moore