Siguiente: Máquinas de Moore Un nivel arriba: Máquinas secuenciales Anterior: Máquinas secuenciales

Máquinas de Mealy

Una máquina de Mealy es una estructura de la forma

$$\mbox{\it MMe\/}=(Q,\mbox{\it Ent\/},\mbox{\it Sal\/},\mbox{\it tran\/},\mbox{\it res\/},q_0)$$

donde

$$\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...}, y} \\ q_0\in Q &:& \mbox{\rm es el estado {\em inicial}.} \end{eqnarray*}$$

La semántica procedimental de la máquina de Mealy es la siguiente:

Al inicio de cualquier computación, la máquina se encuentra en el estado q₀. Posteriormente, cuando la máquina se encuentra en un estado $q\in Q$, y recibe una literal de entrada $e\in\mbox{\it Ent\/}$, entonces emite el símbolo de salida $s=\mbox{\it res\/}(q,e)$ y transita al nuevo estado $p=\mbox{\it tran\/}(q,e)$.

Gráficamente, representamos esto de la siguiente manera:

q0 es el estado inicial.	Si se está en q y llega e entonces se emite $s=\mbox{\it res\/}(q,e)$ y se transita a $p=\mbox{\it tran\/}(q,e)$.

Ejemplos 1. Residuos módulo 4: Si $n\in I\!\!N$ entonces $\overline{n}^1=1^{(n)}$ es la representación unaria de n. Presentaremos una máquina que calcula el residuo módulo 4, de una cadena de 1's, cuando se ve a esa cadena como la representación unaria de un número no-negativo. Representamos gráficamente a la máquina en la figura (3.1-a).

  

Figure 3.1: Máquina de Mealy para el cálculo de residuos módulo 4 en representación unaria.

Esta máquina es $M_{\mbox{\scriptsize mod }4}=(\{q_0,q_1,q_2,q_3\},\{1\},\{0,1,2,3\},\mbox{\it tran\/},\mbox{\it res\/},q_0)$ donde las funciones tran y res están dadas como sendas tablas en la figura (3.1-b). Aquí se puede confundir el conjunto de estados con el alfabeto de salida de manera muy natural: el i-ésimo estado es un i-ésimo símbolo de salida.


2. Repetición final de un mismo símbolo: Construyamos una máquina de Mealy que reconozca a las palabras en (0+1) que terminan con la repetición de un mismo símbolo. Es decir, que reconozca a palabras en el alfabeto L=(0+1)^*(00+11). Gráficamente, presentamos a la máquina en la figura (3.2).

  

Figure 3.2: Máquina de Mealy para reconocer palabras que terminan con un símbolo repetido.

La interpretación de cada estado es natural:

$$\begin{eqnarray*}q_0 &:& \mbox{\rm estado inicial,} \\ p_0 &:& \mbox{\rm estad... ...\ p_1 &:& \mbox{\rm estado de \lq\lq {\em haber llegado un }1''.} \end{eqnarray*}$$

Se tiene una respuesta afirmativa cuándo se permanece en un mismo estado. Las componentes de la máquina son pues $Q=\{q_0,p_0,p_1\}$, $\mbox{\it Ent\/}=\{0,1\}$, $\mbox{\it Sal\/}=\{n,s\}$ y

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

3. Máquina expendedora de golosinas: Consideremos una máquina expendedora de golosinas, de $4 pesos cada una, que recibe monedas de $1, $2, $5 y $10 pesos. Supongamos que la máquina funciona bajo los siguientes supuestos:

• el costo de las golosinas puede cubrirse con cualquier combinación de monedas aceptables,
• la máquina sólo da cambio en monedas de $1 peso, las cuales están almacenadas en una alcancía. Si no puede dar cambio, es decir, si el contenido de la alcancía no es suficiente, regresa la moneda insertada, y
• sólo se puede insertar monedas en orden inverso a su denominación.

Codifiquemos el funcionamiento de la máquina con los conjuntos siguientes:

• Monedas a insertarse:
  
  $$\begin{eqnarray*}m_0 &:& \mbox{\rm ninguna moneda se inserta,} \\ m_1 &:& \mbo... ...cinco pesos,} \\ m_{10} &:& \mbox{\rm moneda de diez pesos.} \end{eqnarray*}$$
  
  
• Respuestas de la máquina:
  
  $$\begin{eqnarray*}s_0 &:& \mbox{\rm contin\'ua sin m\'as,} \\ s_1 &:& \mbox{\rm... ...cambio,} \\ s_3 &:& \mbox{\rm devuelve la moneda insertada.} \end{eqnarray*}$$
  
  
• Estados de la máquina:
  
  $$\begin{eqnarray*}q_0 &:& \mbox{\rm estado inicial}, \\ \forall i\in[0,5]:a_i &... ...por pagar $k$\space pesos cuando se inici\'o el pago con \$1.} \end{eqnarray*}$$
  
  
• Depósito en la alcancía:
  
  $$\begin{eqnarray*}\forall i\in[1,6]:p_i &:& \mbox{\rm NO alcanza a haber $i$\space pesos,} \\ p_7 &:& \mbox{\rm al menos hay \$6 pesos.} \end{eqnarray*}$$
  
  

La máquina de Mealy que modela el funcionamiento de la máquina expendedora tiene como alfabeto de entrada el producto cartesiano del conjunto de monedas aceptables con el conjunto que codifica a los depósitos de la alcancía. Hay pues $5\times 7=35$ símbolos de entrada $m_{\mu}p_{\nu}$. El alfabeto de salida está dado por las 4 posibles respuestas que da la máquina expendedora. Hay 1+6+2+3=12 estados. A grandes rasgos las transiciones se definen como se muestra en las tablas (3.1) y (3.2).

 

Table 3.1: Transiciones y repuestas de la máquina expendedora.

$\begin{array}[t]{rcl} \forall j\leq 6: && \\ \mbox{\it tran\/}(q_0,m_{10}p_j) &=& q_0 \\ \mbox{\it res\/}(q_0,m_{10}p_j) &=& s_3 \end{array}$	si se inserta una moneda de $10 pesos y no hay cambio suficiente, se devuelve la moneda y se reinicia el proceso,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(q_0,m_{10}p_7) &=& a_5 \\ \mbox{\it res\/}(q_0,m_{10}p_7) &=& s_2 \end{array}$	ya que lo hay, procédase a dar cambio,
$\begin{array}[t]{rcl} \forall k=5,4,3,2,1: && \\ \mbox{\it tran\/}(a_{k},m_{0}P) &=& a_{k-1} \\ \mbox{\it res\/}(a_{k},m_{0}P) &=& s_2 \end{array}$	para P=pj, cualquiera que sea j, continúese devolviendo un peso hasta completar el cambio. Obsérvese que aquí, en principio, puede haber combinaciones (ak,pj) contradictorias. Sin embargo, la interpretación que se está construyendo excluye que aparezcan esas inconsistencias.
$\begin{array}[t]{rcl} \mbox{\it tran\/}(a_{0},m_{0}P) &=& q_0 \\ \mbox{\it res\/}(a_{0},m_{0}P) &=& s_1 \end{array}$	al terminar de dar el cambio, se entrega la golosina y se reinicia el proceso.

 

Table 3.2: Transiciones y repuestas de la máquina expendedora (cont).

$\begin{array}[t]{rcl} \mbox{\it tran\/}(q_0,m_{5}p_1) &=& q_0 \\ \mbox{\it res\/}(q_0,m_{5}p_1) &=& s_3 \end{array}$	si se inserta una moneda de $5 pesos y no hay cambio, se devuelve la moneda y se reinicia el proceso,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(q_0,m_{5}P) &=& a_0 \\ \mbox{\it res\/}(q_0,m_{5}P) &=& s_2 \end{array}$	si hay monedas en la alcancía, i.e. $P\not=p_1$, entonces se da el peso de cambio,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(q_0,m_{2}P) &=& b_2 \\ \mbox{\it res\/}(q_0,m_{2}P) &=& s_0 \end{array}$	se insertan $2 pesos y se espera a completar el importe de $4 pesos,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(b_2,m_{2}P) &=& q_0 \\ \mbox{\it res\/}(b_2,m_{2}P) &=& s_1 \end{array}$	habiéndose completado el costo de la golosina, se lo entrega y se reinicia el proceso,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(b_2,m_{1}P) &=& c_1 \\ \mbox{\it res\/}(b_2,m_{1}P) &=& s_0 \end{array}$	se inserta un peso más y hay que esperar a que llegue el último,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(b_2,MP) &=& b_2 \\ \mbox{\it res\/}(b_2,MP) &=& s_3 \end{array}$	si llega una moneda con denominación mayor M=m5,m10 entonces se la devuelve y se continúa la espera,
$\begin{array}[t]{rcl} \mbox{\it tran\/}(q_0,m_{1}P) &=& c_3 \\ \mbox{\it res\/}(q_0,m_{1}P) &=& s_0 \end{array}$	si se inicia el pago con una moneda de un peso hya que esperar los otros tres pesos,
$\begin{array}[t]{rcl} \forall k=3,2,1:&& \\ \mbox{\it tran\/}(c_{k},m_{1}P) &=& c_{k-1} \\ \mbox{\it res\/}(c_{k},m_{1}P) &=& s_0 \end{array}$	se continúa el pago, recibiendo un peso a la vez. Aquí c0=a0. Si se recibe monedas de mayor denominación, se develve éstas.
	cualquier otra posibilidad (Estado,Entrada) es inconsistente e inalcanzable en la máquina.

Siguiente: Máquinas de Moore Un nivel arriba: Máquinas secuenciales Anterior: Máquinas secuenciales