Moore e Mealy Machines
Gli automi finiti possono avere uscite corrispondenti a ciascuna transizione. Esistono due tipi di macchine a stati finiti che generano output:
- Macchina farinosa
- Macchina di Moore
Macchina farinosa
Una Mealy Machine è una FSM il cui output dipende dallo stato attuale e dall'input presente.
Può essere descritto da una tupla 6 (Q, ∑, O, δ, X, q 0 ) dove -
Q è un insieme finito di stati.
∑ è un insieme finito di simboli chiamato alfabeto di input.
O è un insieme finito di simboli chiamato alfabeto di output.
δ è la funzione di transizione di ingresso dove δ: Q × ∑ → Q
X è la funzione di transizione dell'uscita dove X: Q × ∑ → O
q0è lo stato iniziale da cui viene elaborato qualsiasi input (q 0 ∈ Q).
La tabella degli stati di una macchina farinosa è mostrata di seguito:
| Stato attuale | Stato successivo | |||
|---|---|---|---|---|
| ingresso = 0 | ingresso = 1 | |||
| Stato | Produzione | Stato | Produzione | |
| → 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 |
Il diagramma di stato della suddetta Mealy Machine è:
Moore Machine
La macchina Moore è una FSM i cui output dipendono solo dallo stato presente.
Una macchina di Moore può essere descritta da una tupla 6 (Q, ∑, O, δ, X, q 0 ) dove -
Q è un insieme finito di stati.
∑ è un insieme finito di simboli chiamato alfabeto di input.
O è un insieme finito di simboli chiamato alfabeto di output.
δ è la funzione di transizione di ingresso dove δ: Q × ∑ → Q
X è la funzione di transizione dell'uscita dove X: Q → O
q0è lo stato iniziale da cui viene elaborato qualsiasi input (q 0 ∈ Q).
La tabella degli stati di una macchina Moore è mostrata di seguito:
| Stato attuale | Stato successivo | Produzione | |
|---|---|---|---|
| Ingresso = 0 | Ingresso = 1 | ||
| → a | b | c | x 2 |
| b | b | d | x 1 |
| c | c | d | x 2 |
| d | d | d | x 3 |
Il diagramma di stato della macchina Moore sopra è:
Mealy Machine contro Moore Machine
La tabella seguente evidenzia i punti che differenziano una Mealy Machine da una Moore Machine.
| Macchina farinosa | Moore Machine |
|---|---|
| L'uscita dipende sia dallo stato presente che dall'ingresso presente | L'output dipende solo dallo stato attuale. |
| In generale, ha meno stati di Moore Machine. | In generale, ha più stati di Mealy Machine. |
| Il valore della funzione di uscita è una funzione delle transizioni e dei cambiamenti, quando viene eseguita la logica di ingresso sullo stato attuale. | Il valore della funzione di uscita è una funzione dello stato corrente e dei cambiamenti ai fronti di clock, ogni volta che si verificano cambiamenti di stato. |
| Le macchine farinose reagiscono più velocemente agli input. Generalmente reagiscono nello stesso ciclo di clock. | Nelle macchine Moore, è necessaria più logica per decodificare le uscite, con conseguenti più ritardi del circuito. Generalmente reagiscono dopo un ciclo di clock. |
Moore Machine to Mealy Machine
Algoritmo 4
Input - Moore Machine
Output - Macchina farinosa
Step 1 - Prendi un formato di tabella di transizione Mealy Machine vuoto.
Step 2 - Copia tutti gli stati di transizione della Moore Machine in questo formato di tabella.
Step 3- Verificare gli stati presenti e le relative uscite nella tabella degli stati della macchina Moore; se per uno stato Q i l' output è m, copiarlo nelle colonne di output della tabella di stato Mealy Machine ovunque Q i appare nello stato successivo.
Esempio
Consideriamo la seguente macchina Moore:
| Stato attuale | Stato successivo | Produzione | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b | 1 |
| b | un | d | 0 |
| c | c | c | 0 |
| d | b | un | 1 |
Ora applichiamo l'algoritmo 4 per convertirlo in Mealy Machine.
Step 1 & 2 -
| Stato attuale | Stato successivo | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Stato | Produzione | Stato | Produzione | |
| → a | d | b | ||
| b | un | d | ||
| c | c | c | ||
| d | b | un | ||
Step 3 -
| Stato attuale | Stato successivo | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Stato | Produzione | Stato | Produzione | |
| => a | d | 1 | b | 0 |
| b | un | 1 | d | 1 |
| c | c | 0 | c | 0 |
| d | b | 0 | un | 1 |
Mealy Machine to Moore Machine
Algoritmo 5
Input - Macchina farinosa
Output - Moore Machine
Step 1- Calcola il numero di differenti uscite per ogni stato (Q i ) che sono disponibili nella tabella degli stati della macchina Mealy.
Step 2- Se tutte le uscite di Qi sono uguali, copia lo stato Q i . Se ha n uscite distinte, spezza Q i in n stati come Q in doven = 0, 1, 2 .......
Step 3 - Se l'uscita dello stato iniziale è 1, inserire un nuovo stato iniziale all'inizio che restituisce 0 output.
Esempio
Consideriamo la seguente macchina farinosa:
| Stato attuale | Stato successivo | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Stato successivo | Produzione | Stato successivo | Produzione | |
| → a | d | 0 | b | 1 |
| b | un | 1 | d | 0 |
| c | c | 1 | c | 0 |
| d | b | 0 | un | 1 |
Qui, gli stati "a" e "d" forniscono rispettivamente solo 1 e 0 output, quindi conserviamo gli stati "a" e "d". Ma gli stati "b" e "c" producono output diversi (1 e 0). Quindi, ci dividiamob in b0, b1 e c in c0, c1.
| Stato attuale | Stato successivo | Produzione | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b 1 | 1 |
| b 0 | un | d | 0 |
| b 1 | un | d | 1 |
| c 0 | c 1 | C 0 | 0 |
| c 1 | c 1 | C 0 | 1 |
| d | b 0 | un | 0 |