Pedagogia

AUTÓMATA DE MEALY

Una Máquina de Mealy (o Transductor de estados finito) también es un autómata finito pero que genera una salida. Es definido por una 6-tupla:


Donde:

: Es el conjunto finito de estados.
: Es el alfabeto de entrada.
: Es el alfabeto de salida.

: Un estado (elemento de ) distinguible en el cual inicia la computación.
: Es la función de transición
: Es lafunción de salida.

Notemos que no se ha definido algún conjunto de estados de salida, puesto que la función de este tipo de máquinas, responde con una cadena de salida ante los símbolos de entrada y los estados correspondientes, de esta manera todos los estados son estados finales y solamente uno de ellos es un estado inicial.
Este tipo de máquinas nos serán especialmente útiles parareconocer subespacios de células, ya que es posible crear una máquina de estados que lea cada valor de cada célula en el subespacio definido y al terminar de leer, genere ciertas palabras. Por ejemplo:
Sea la máquina de Mealy definida como sigue:
, done cada elemento es definido así:



:

:

En la descripción del ejemplo anterior, las funciones y se describen como tercias, endonde el tercer elemento de cada triada es el resultado de la función aplicada a los dos primeros elementos de la tercia en ese orden. El diagrama de transiciones entre los estados se muestra en la figura 1 , donde los símbolos del alfabeto de entrada se muestran en las etiquetas de las flechas en color negro en la parte izquierda de la etiqueta, y los símbolos del alfabeto de salida se muestranen el lado derecho de la etiqueta de cada liga en color rojo 1


Figura 1: Diagrama de transición de estados de la máquina de Mealy del ejemplo 1 .

Al desarrollar el funcionamiento de esta máquina, nos podemos dar cuenta de que la función de salida devuelve un 1 únicamente cuando se proporciona como entrada una cadena binaria del tipo 1(011)+, donde la palabra generada por es del tipo0(001)+ dándonos la oportunidad de verificar el último carácter para determinar alguna acción: si el último carácter es 1, entonces se realiza tal, de otra manera no se realiza.


1.- Residuos Modulo 4: Acentuació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. Representamosgráficamente a la máquina en la figura (3.1-a).
Figura 3.1: Máquina de Mealy para el cálculo de residuos módulo 4 en representación unaria.





Esta máquina es 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).
Figura 3.2: Máquina de Mealy para reconocer palabras que terminan con un símbolo repetido.




Lainterpretación de cada estado es natural:


Se tiene una respuesta afirmativa cuándo se permanece en un mismo estado. Las componentes de la máquina son pues y

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:
Elcosto 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...