Mquina de MealyA Mquina de Mealy um Autmato Finito modificado de forma a gerar uma palavra de sada para cada transio.DEFINIO:

Uma Mquina de Mealy M Autmato Finito Determinstico com sadas associadas s transies. representada por uma 6-upla:M = (, Q , , q0, F, )Onde:alfabeto de smbolos de entrada;Qconjunto de estados possveis do autmato o qual finito;funo programa ou funo transio::Q x Q x *a qual uma funo parcial;q0estado inicial do autmato tal que q0 elemento de Q;Fconjunto de estados finais tal que F est contido em Q; alfabeto de smbolos de saida.

Portanto, as componentes , Q, q0 e F so como no Autmato Finito Determinstico. A funo programa pode ser representada como um grafo finito direto como nos AFD, adicionando, na etiqueta de cada transio, a sada associada, quando diferente da palavra vazia.O processamento de uma Mquina de Mealy, para uma palavra de entrada W, consiste na sucessiva aplicao da funo programa para cada smbolo de w (da esquerda para a direita) at ocorrer uma condio de parada.A palavra vazia como sada da funo programa indica que nenhuma gravao realizada e, obviamente, no move a cabea da fita de sada. Se todas as transies geram sada vazia, ento a Mquina de Mealy processa como se fosse um Autmato Finito. A definio formal da funo programa estendida de uma Mquina de Mealy sugerida como exerccio.

EXEMPLO:Uma aplicao comum frequentemente recomendada para os autmatos com sada o projeto de dilogo entre um programa (de computador) e o seu usario. Basicamente, um dilogo pode ser de dois tipos: Comandado pelo programa Comandado pelo usurioEm qualquer caso, uma das principais dificuldades do projetista a visualizao do conjunto de eventos e aes que definam um dilogo adequado para as diversas situaes possveis.O exemplo que segue uma Mquina de Mealy que trata de algumas situaes tpicas de um dilogo que cria e atualiza arquivos. A seguinte simbologia adotada no grafo da funo de transio: : entrada fornecida pelo usurio (em um teclado, por exemplo); ...: sada gerada pelo programa (em um vdeo, por exemplo); [...] : ao interna ao programa, sem comunicao com o usurio; (...) : resultado de uma ao interna ao programa; usado como portugus) vlidos no dilogo.A Mquina de Mealy M = (, {q0,q1 ..., q8,qf}, , q0,{qf}, ) como ilustrada na figura abaixo, onde = e representam o conjunto de smbolos (palavras do portugus) vlidos no dilogo.

Mquina de MooreA Mquina de Moore possui uma segunda funo, que gera uma palavra de sada (que pode ser vazia) para cada estado da mquina.DEFINIO:Uma mquina de Moore M um Autmato Finito Determinstico com sadas associadas aos estados. representada por uma 7-upla:M = (, Q , , q0, F, , s)Onde:alfabeto de smbolos de entrada;Qconjunto de estados possveis do autmato o qual finito;funo programa ou funo transio::Q x Qa qual uma funo parcial;q0estado inicial do autmato tal que q0 elemento de Q;Fconjunto de estados finais tal que F est contido em Q; alfabeto de smbolos de saida.s funo de sada:s: Q*a qual uma funo total.Portanto os componentes , Q, , q0 e F so como no Autmato Finito Determinstico e como na Mquina de Mealy. A funo programa pode ser representada como um grafo finito direto como nos AFD, adicionando, na etiqueta de cada estado, a sada associada, quando diferente da palavra vazia.O processamento de uma Mquina de Moore, para uma palavra de entrada W, consiste na sucessiva aplicao da funo programa para cada smbolo de W ( da esquerda para a direita) at ocorrer uma condio de parada.A palavra vazia resultado da funo de sada indica que nenhuma gravao realizada e, obviamente, no move a cabea da fita de sada. Se todos os estados geram a sada vazia, ento a Mquina de Moore processa como se fosse um Autmato Finito. A definio formal da funo programa estendida de uma Mquina de Moore sugerida como exerccio.EXEMPLO:Um exemplo comum de aplicao do conceito de Mquina de Moore o desenvolvimento de Analisadores Lxicos de compiladores ou tradutores de linguagens em geral. Basicamente, um analisador lxico um Autmato Finito ( em geral determinstico) que identifica os componentes bsicos da linguagem como, por exemplo, nmeros, identificadores, separadores, etc.Uma Mquina de Moore como um Analisador Lxico como segue: Um estado final associado a cada unidade lxica; Cada estado final possui uma sada (definida pela Funo de Sada) que descreve ou codifica a unidade lxica identificada; Para os demais estados (no finais) a sada gerara a palavra vazia.