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