Máquinas Moore e Mealy

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

  • Mealy Machine
  • Máquina de moore

Mealy Machine

Uma máquina Mealy é um FSM cuja saída depende do estado atual, bem como da entrada atual.

Pode ser descrito por uma 6 tupla (Q, ∑, O, δ, X, q 0 ) onde -

  • Q é um conjunto finito de estados.

  • ∑ é um conjunto finito de símbolos denominado alfabeto de entrada.

  • O é um conjunto finito de símbolos chamado alfabeto de saída.

  • δ é a função de transição de entrada onde δ: Q × ∑ → Q

  • X é a função de transição de saída onde X: Q × ∑ → O

  • q0é o estado inicial de onde qualquer entrada é processada (q 0 ∈ Q).

A tabela de estado de uma máquina Mealy é mostrada abaixo -

Estado atual Próximo estado
entrada = 0 entrada = 1
Estado Resultado Estado Resultado
→ a b x 1 c x 1
b b x 2 d x 3
c d x 3 c x 1
d d x 3 d x 2

O diagrama de estado da Mealy Machine acima é -

Moore Machine

A máquina de Moore é um FSM cujas saídas dependem apenas do estado atual.

Uma máquina de Moore pode ser descrita por uma tupla de 6 (Q, ∑, O, δ, X, q 0 ) onde -

  • Q é um conjunto finito de estados.

  • ∑ é um conjunto finito de símbolos denominado alfabeto de entrada.

  • O é um conjunto finito de símbolos chamado alfabeto de saída.

  • δ é a função de transição de entrada onde δ: Q × ∑ → Q

  • X é a função de transição de saída onde X: Q → O

  • q0é o estado inicial de onde qualquer entrada é processada (q 0 ∈ Q).

A tabela de estado de uma Máquina Moore é mostrada abaixo -

Estado atual Próximo estado Resultado
Entrada = 0 Entrada = 1
→ a b c x 2
b b d x 1
c c d x 2
d d d x 3

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

Máquina Mealy vs. Máquina Moore

A tabela a seguir destaca os pontos que diferenciam uma Máquina Mealy de uma Máquina Moore.

Mealy Machine Moore Machine
A saída depende do estado atual e da entrada atual A saída depende apenas do estado atual.
Geralmente, ele tem menos estados do que a Máquina Moore. Geralmente, ele tem mais estados do que a Máquina Mealy.
O valor da função de saída é uma função das transições e mudanças, quando a lógica de entrada no estado atual é feita. O valor da função de saída é uma função do estado atual e das mudanças nas bordas do clock, sempre que ocorrerem mudanças de estado.
As máquinas Mealy reagem mais rápido às entradas. Eles geralmente reagem no mesmo ciclo de clock. Em máquinas Moore, mais lógica é necessária para decodificar as saídas, resultando em mais atrasos no circuito. Eles geralmente reagem um ciclo de clock depois.

Máquina Moore para Máquina Mealy

Algoritmo 4

Input - Máquina Moore

Output - Máquina Mealy

Step 1 - Pegue um formato de tabela de transição da Máquina Mealy em branco.

Step 2 - Copie todos os estados de transição da Máquina Moore para este formato de tabela.

Step 3- Verifique os estados atuais e suas saídas correspondentes na tabela de estados da Máquina Moore; se para um estado Q i a saída for m, copie-o nas colunas de saída da tabela de estado da Máquina Mealy sempre que Q i aparecer no próximo estado.

Exemplo

Vamos considerar a seguinte máquina de Moore -

Estado atual Próximo estado Resultado
a = 0 a = 1
→ a d b 1
b uma d 0
c c c 0
d b uma 1

Agora aplicamos o Algoritmo 4 para convertê-lo em Máquina Mealy.

Step 1 & 2 -

Estado atual Próximo estado
a = 0 a = 1
Estado Resultado Estado Resultado
→ a d b
b uma d
c c c
d b uma

Step 3 -

Estado atual Próximo estado
a = 0 a = 1
Estado Resultado Estado Resultado
=> a d 1 b 0
b uma 1 d 1
c c 0 c 0
d b 0 uma 1

Máquina Mealy para Máquina Moore

Algoritmo 5

Input - Máquina Mealy

Output - Máquina Moore

Step 1- Calcule o número de saídas diferentes para cada estado (Q i ) que estão disponíveis na tabela de estados da máquina Mealy.

Step 2- Se todas as saídas de Qi forem iguais, copie o estado Q i . Se tiver n saídas distintas, divida Q i em n estados como Q em onden = 0, 1, 2 .......

Step 3 - Se a saída do estado inicial for 1, insira um novo estado inicial no início que forneça 0 saída.

Exemplo

Vamos considerar a seguinte Máquina Mealy -

Estado atual Próximo estado
a = 0 a = 1
Próximo estado Resultado Próximo estado Resultado
→ a d 0 b 1
b uma 1 d 0
c c 1 c 0
d b 0 uma 1

Aqui, os estados 'a' e 'd' fornecem apenas 1 e 0 saídas, respectivamente, portanto, retemos os estados 'a' e 'd'. Mas os estados 'b' e 'c' produzem resultados diferentes (1 e 0). Então, nós dividimosb para dentro b0, b1 e c para dentro c0, c1.

Estado atual Próximo estado Resultado
a = 0 a = 1
→ a d b 1 1
b 0 uma d 0
b 1 uma d 1
c 0 c 1 C 0 0
c 1 c 1 C 0 1
d b 0 uma 0