Moore und mehlige Maschinen
Endliche Automaten können Ausgaben haben, die jedem Übergang entsprechen. Es gibt zwei Arten von Finite-State-Maschinen, die Ausgabe generieren:
- Mehlige Maschine
- Moore Maschine
Mehlige Maschine
Eine mehlige Maschine ist ein FSM, dessen Ausgabe sowohl vom aktuellen Zustand als auch von der aktuellen Eingabe abhängt.
Es kann durch ein 6-Tupel (Q, ∑, O, δ, X, q 0 ) beschrieben werden, wobei -
Q ist eine endliche Menge von Zuständen.
∑ ist eine endliche Menge von Symbolen, die als Eingabealphabet bezeichnet wird.
O ist eine endliche Menge von Symbolen, die als Ausgabealphabet bezeichnet wird.
δ ist die Eingangsübergangsfunktion, wobei δ: Q × ∑ → Q.
X ist die Ausgangsübergangsfunktion, wobei X: Q × ∑ → O.
q0ist der Anfangszustand, von dem aus eine Eingabe verarbeitet wird (q 0 ∈ Q).
Die Statustabelle einer mehligen Maschine ist unten dargestellt -
Derzeitiger Zustand | Nächster Zustand | |||
---|---|---|---|---|
Eingabe = 0 | Eingabe = 1 | |||
Zustand | Ausgabe | Zustand | Ausgabe | |
→ 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 |
Das Zustandsdiagramm der obigen Mealy Machine ist -
Moore Machine
Die Moore-Maschine ist eine FSM, deren Ausgänge nur vom aktuellen Zustand abhängen.
Eine Moore-Maschine kann durch ein 6-Tupel (Q, ∑, O, δ, X, q 0 ) beschrieben werden, wobei -
Q ist eine endliche Menge von Zuständen.
∑ ist eine endliche Menge von Symbolen, die als Eingabealphabet bezeichnet wird.
O ist eine endliche Menge von Symbolen, die als Ausgabealphabet bezeichnet wird.
δ ist die Eingangsübergangsfunktion, wobei δ: Q × ∑ → Q.
X ist die Ausgangsübergangsfunktion, wobei X: Q → O.
q0ist der Anfangszustand, von dem aus eine Eingabe verarbeitet wird (q 0 ∈ Q).
Die Statustabelle einer Moore-Maschine ist unten dargestellt -
Derzeitiger Zustand | Nächster Zustand | Ausgabe | |
---|---|---|---|
Eingabe = 0 | Eingabe = 1 | ||
→ a | b | c | x 2 |
b | b | d | x 1 |
c | c | d | x 2 |
d | d | d | x 3 |
Das Zustandsdiagramm der obigen Moore-Maschine lautet -
Mehlige Maschine gegen Moore-Maschine
In der folgenden Tabelle sind die Punkte aufgeführt, die eine mehlige Maschine von einer Moore-Maschine unterscheiden.
Mehlige Maschine | Moore Machine |
---|---|
Die Ausgabe hängt sowohl vom aktuellen Zustand als auch von der aktuellen Eingabe ab | Die Ausgabe hängt nur vom aktuellen Zustand ab. |
Im Allgemeinen hat es weniger Zustände als Moore Machine. | Im Allgemeinen hat es mehr Zustände als Mealy Machine. |
Der Wert der Ausgangsfunktion ist eine Funktion der Übergänge und der Änderungen, wenn die Eingangslogik für den aktuellen Zustand abgeschlossen ist. | Der Wert der Ausgangsfunktion ist eine Funktion des aktuellen Zustands und der Änderungen an den Taktflanken, wenn Zustandsänderungen auftreten. |
Mehlige Maschinen reagieren schneller auf Eingaben. Sie reagieren im Allgemeinen im gleichen Taktzyklus. | In Moore-Maschinen ist mehr Logik erforderlich, um die Ausgänge zu decodieren, was zu mehr Schaltungsverzögerungen führt. Sie reagieren in der Regel einen Taktzyklus später. |
Moore Machine zu Mealy Machine
Algorithmus 4
Input - Moore Machine
Output - Mehlige Maschine
Step 1 - Nehmen Sie ein leeres Mealy Machine-Übergangstabellenformat.
Step 2 - Kopieren Sie alle Moore Machine-Übergangszustände in dieses Tabellenformat.
Step 3- Überprüfen Sie den aktuellen Status und die entsprechenden Ausgänge in der Moore Machine-Statustabelle. Wenn für einen Zustand Q i die Ausgabe m ist, kopieren Sie ihn in die Ausgabespalten der Mealy Machine-Statustabelle, wo immer Q i im nächsten Zustand erscheint.
Beispiel
Betrachten wir die folgende Moore-Maschine -
Derzeitiger Zustand | Nächster Zustand | Ausgabe | |
---|---|---|---|
a = 0 | a = 1 | ||
→ a | d | b | 1 |
b | ein | d | 0 |
c | c | c | 0 |
d | b | ein | 1 |
Jetzt wenden wir Algorithmus 4 an, um ihn in Mealy Machine zu konvertieren.
Step 1 & 2 - -
Derzeitiger Zustand | Nächster Zustand | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Zustand | Ausgabe | Zustand | Ausgabe | |
→ a | d | b | ||
b | ein | d | ||
c | c | c | ||
d | b | ein |
Step 3 - -
Derzeitiger Zustand | Nächster Zustand | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Zustand | Ausgabe | Zustand | Ausgabe | |
=> a | d | 1 | b | 0 |
b | ein | 1 | d | 1 |
c | c | 0 | c | 0 |
d | b | 0 | ein | 1 |
Mehlige Maschine zu Moore Maschine
Algorithmus 5
Input - Mehlige Maschine
Output - Moore Machine
Step 1- Berechnen Sie die Anzahl der verschiedenen Ausgänge für jeden Zustand (Q i ), die in der Zustandstabelle der Mealy-Maschine verfügbar sind.
Step 2- Wenn alle Ausgänge von Qi gleich sind, kopieren Sie den Status Q i . Wenn es n verschiedene Ausgänge hat, teilen Sie Q i in n Zustände als Q in won = 0, 1, 2 .......
Step 3 - Wenn der Ausgang des Ausgangszustands 1 ist, fügen Sie am Anfang einen neuen Ausgangszustand ein, der den Ausgang 0 ergibt.
Beispiel
Betrachten wir die folgende mehlige Maschine -
Derzeitiger Zustand | Nächster Zustand | |||
---|---|---|---|---|
a = 0 | a = 1 | |||
Nächster Zustand | Ausgabe | Nächster Zustand | Ausgabe | |
→ a | d | 0 | b | 1 |
b | ein | 1 | d | 0 |
c | c | 1 | c | 0 |
d | b | 0 | ein | 1 |
Hier geben die Zustände 'a' und 'd' nur 1 bzw. 0 Ausgänge, so dass wir die Zustände 'a' und 'd' beibehalten. Die Zustände 'b' und 'c' erzeugen jedoch unterschiedliche Ausgaben (1 und 0). Also teilen wir unsb in b0, b1 und c in c0, c1.
Derzeitiger Zustand | Nächster Zustand | Ausgabe | |
---|---|---|---|
a = 0 | a = 1 | ||
→ a | d | b 1 | 1 |
b 0 | ein | d | 0 |
b 1 | ein | d | 1 |
c 0 | c 1 | C 0 | 0 |
c 1 | c 1 | C 0 | 1 |
d | b 0 | ein | 0 |