Maszyny Moore i Mealy
Automaty skończone mogą mieć wyjścia odpowiadające każdemu przejściu. Istnieją dwa typy maszyn o skończonych stanach, które generują dane wyjściowe -
- Mączna Maszyna
- Maszyna Moore'a
Mączna Maszyna
Maszyna Mealy to FSM, którego wyjście zależy od aktualnego stanu, jak również od aktualnego wejścia.
Można to opisać za pomocą 6 krotek (Q, ∑, O, δ, X, q 0 ), gdzie -
Q jest skończonym zbiorem stanów.
∑ jest skończonym zbiorem symboli zwanym alfabetem wejściowym.
O jest skończonym zbiorem symboli zwanym alfabetem wyjściowym.
δ jest funkcją przejścia wejściowego, gdzie δ: Q × ∑ → Q
X jest funkcją przejścia wyjściowego, gdzie X: Q × ∑ → O
q0jest stanem początkowym, z którego przetwarzane jest dowolne wejście (q 0 ∈ Q).
Tabela stanów Mealy Machine jest pokazana poniżej -
| Stan obecny | Następny stan | |||
|---|---|---|---|---|
| wejście = 0 | wejście = 1 | |||
| Stan | Wynik | Stan | Wynik | |
| → a | b | x 1 | do | x 1 |
| b | b | x 2 | re | x 3 |
| do | re | x 3 | do | x 1 |
| re | re | x 3 | re | x 2 |
Schemat stanu powyższej Mealy Machine to -
Moore Machine
Maszyna Moore'a to FSM, którego wyniki zależą tylko od aktualnego stanu.
Maszynę Moore'a można opisać za pomocą 6 krotek (Q, ∑, O, δ, X, q 0 ), gdzie -
Q jest skończonym zbiorem stanów.
∑ jest skończonym zbiorem symboli zwanym alfabetem wejściowym.
O jest skończonym zbiorem symboli zwanym alfabetem wyjściowym.
δ jest funkcją przejścia wejściowego, gdzie δ: Q × ∑ → Q
X jest funkcją przejścia wyjściowego, gdzie X: Q → O
q0jest stanem początkowym, z którego przetwarzane jest dowolne wejście (q 0 ∈ Q).
Tabela stanów maszyny Moore jest pokazana poniżej -
| Stan obecny | Następny stan | Wynik | |
|---|---|---|---|
| Wejście = 0 | Wejście = 1 | ||
| → a | b | do | x 2 |
| b | b | re | x 1 |
| do | do | re | x 2 |
| re | re | re | x 3 |
Schemat stanu powyższej Maszyny Moore to -
Mealy Machine vs Moore Machine
Poniższa tabela przedstawia punkty, które odróżniają maszynę Mealy od maszyny Moore.
| Mączna Maszyna | Moore Machine |
|---|---|
| Wyjście zależy zarówno od aktualnego stanu, jak i aktualnego wejścia | Wynik zależy tylko od aktualnego stanu. |
| Generalnie ma mniej stanów niż Moore Machine. | Generalnie ma więcej stanów niż Mealy Machine. |
| Wartość funkcji wyjściowej jest funkcją przejść i zmian, gdy logika wejściowa jest zakończona. | Wartość funkcji wyjściowej jest funkcją aktualnego stanu i zmian na krawędziach zegara, ilekroć zachodzą zmiany stanu. |
| Maszyny Mealy szybciej reagują na dane wejściowe. Na ogół reagują w tym samym cyklu zegara. | W maszynach Moore'a potrzeba więcej logiki do dekodowania wyjść, co skutkuje większymi opóźnieniami obwodów. Zwykle reagują o jeden cykl zegara później. |
Moore Machine to Mealy Machine
Algorytm 4
Input - Maszyna Moore'a
Output - Maszyna Mączna
Step 1 - Weź pusty format tabeli przejścia Mealy Machine.
Step 2 - Skopiuj wszystkie stany przejścia Moore Machine do tego formatu tabeli.
Step 3- Sprawdź obecne stany i odpowiadające im wyjścia w tabeli stanów Maszyny Moore'a; jeśli dla stanu Q i wyjście jest m, skopiuj je do kolumn wyjściowych tabeli stanów Mealy Machine, gdziekolwiek Q i pojawi się w następnym stanie.
Przykład
Rozważmy następującą maszynę Moore'a -
| Stan obecny | Następny stan | Wynik | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | re | b | 1 |
| b | za | re | 0 |
| do | do | do | 0 |
| re | b | za | 1 |
Teraz stosujemy algorytm 4, aby przekonwertować go na Mealy Machine.
Step 1 & 2 -
| Stan obecny | Następny stan | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Stan | Wynik | Stan | Wynik | |
| → a | re | b | ||
| b | za | re | ||
| do | do | do | ||
| re | b | za | ||
Step 3 -
| Stan obecny | Następny stan | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Stan | Wynik | Stan | Wynik | |
| => a | re | 1 | b | 0 |
| b | za | 1 | re | 1 |
| do | do | 0 | do | 0 |
| re | b | 0 | za | 1 |
Mealy Machine to Moore Machine
Algorytm 5
Input - Maszyna Mączna
Output - Maszyna Moore'a
Step 1- Oblicz liczbę różnych wyjść dla każdego stanu (Q i ), które są dostępne w tabeli stanów maszyny Mealy.
Step 2- Jeśli wszystkie wyjścia Qi są takie same, skopiuj stan Q i . Jeśli ma n różnych wyjść, przerwy P I do n stanów jako Q w którymn = 0, 1, 2 .......
Step 3 - Jeśli wyjście stanu początkowego ma wartość 1, wstaw nowy stan początkowy na początku, który daje wyjście 0.
Przykład
Rozważmy następującą Mealy Machine -
| Stan obecny | Następny stan | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Następny stan | Wynik | Następny stan | Wynik | |
| → a | re | 0 | b | 1 |
| b | za | 1 | re | 0 |
| do | do | 1 | do | 0 |
| re | b | 0 | za | 1 |
Tutaj stany „a” i „d” dają odpowiednio tylko 1 i 0 wyjść, więc zachowujemy stany „a” i „d”. Ale stany „b” i „c” dają różne wyniki (1 i 0). Więc dzielimy sięb w b0, b1 i c w c0, c1.
| Stan obecny | Następny stan | Wynik | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | re | b 1 | 1 |
| b 0 | za | re | 0 |
| b 1 | za | re | 1 |
| c 0 | c 1 | C 0 | 0 |
| c 1 | c 1 | C 0 | 1 |
| re | b 0 | za | 0 |