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 |