As Máquinas de Mealy e Moore - Autômatos

Introdução

As máquinas de estado finito são críticas para a realização da lógica de controle e tomada de decisão nos sistemas digitais. Por que eles são chamados de máquinas de estados finitos?

É porque a lógica sequencial que os implementa pode estar em apenas um número fixo de estados. Nas máquinas de estados finitas, as saídas e o próximo estado são uma função da entrada e do estado presente. Isso significa que a escolha do próximo estado pode depender do valor de uma entrada e levar a um comportamento mais complexo do sistema. Como na lógica sequencial, precisamos do histórico passado de entradas para determinar a saída, portanto a máquina de estados finitos se mostra muito útil na realização de funções lógicas sequenciais. Existem basicamente duas maneiras pelas quais podemos organizar um projeto sequencial. Estas são as implementações da máquina Moore e do design de máquinas Mealy.

Máquinas de Mealy e Moore

Autômatos finitos podem ter saídas correspondentes a cada transição. Existem dois tipos de máquinas de estados finitos que geram saídas.

• Maquina Mealy
• Máquina Moore

Máquina Moore

A máquina Moore são máquinas de estado finito com valor de saída e sua saída depende apenas do estado atual. Pode ser definido como (Q, q0,  ∑,  O, δ, λ) onde:

• Q é um conjunto finito de estados.
• q0 é o estado inicial.
• ∑  é o alfabeto de entrada.
• O é o alfabeto de saída.
• δ é a função de transição que mapeia Q × ∑  → Q.
• λ é a função de saída que mapeia Q → O.

O diagrama de estado da Máquina Moore acima é –

Figura 1

[pic 1]

Na máquina moore mostrada na Figura 1, a saída é representada com cada estado de entrada separado por /. O comprimento da saída para uma máquina moore é maior que a entrada em 1.

• Entrada:  11
• Transição:  δ (q0,11) => δ (q2,1) => q2
• Saída:  000 (0 para q0, 0 para q2 e novamente 0 para q2)

Máquina Mealy.

As máquinas Mealy também são máquinas de estado finito com valor de saída e sua saída depende do estado atual e do símbolo de entrada atual. Pode ser definido como (Q, q0,  ∑,  O, δ, λ ') onde:

• Q é um conjunto finito de estados.
• q0 é o estado inicial.
• ∑  é o alfabeto de entrada.
• O é o alfabeto de saída.
• δ é a função de transição que mapeia Q × ∑  → Q.
• 'λ' é a função de saída que mapeia Q × ∑ → O.·.

O diagrama de estado da Mealy Machine abaixo é –

Figura 2

[pic 2]
                        

Na máquina manual mostrada na Figura 1, a saída é representada com cada símbolo de entrada para cada estado separado por /. O comprimento da saída para uma máquina côncava é igual ao comprimento da entrada.

• Entrada: 11
• Transição:  δ (q0,11) => δ (q2,1) => q2
• Saída:  00 (q0 para q2 transição tem saída 0 e q2 para q2 transição também tem saída 0)

Conversão de Mealy para Moore.

Vamos pegar a tabela de transição da máquina mealy mostrada na Figura 1.

Tabela 1

Etapa 1.  Primeiro, descubra os estados que têm mais de 1 saídas associadas a eles. q1 e q2 são os estados que possuem ambas as saídas 0 e 1 associadas a eles.

Etapa 2.  Crie dois estados para esses estados. Para q1, dois estados serão q10 (estado com saída 0) e q11 (estado com saída 1). Similarmente para q2, dois estados serão q20 e q21.

Etapa 3.  Crie uma máquina moore vazia com o novo estado gerado. Para a máquina moore, a saída será associada a cada estado, independentemente das entradas.

Tabela 2

Etapa 4.  Preencha as entradas do próximo estado usando a tabela de transição de máquina côncava mostrada na Tabela 1. Para q0 na entrada 0, o próximo estado é q10 (q1 com saída 0). Da mesma forma, para q0 na entrada 1, o próximo estado é q20 (q2 com saída 0). Para q1 (ambos q10 e q11) na entrada 0, o próximo estado é q10. Da mesma forma, para q1 (ambos q10 e q11), o próximo estado é q21. Para q10, a saída será 0 e, para q11, a saída será 1. Da mesma forma, outras entradas podem ser preenchidas.

...