Mesin Moore dan Mealy

Automata hingga mungkin memiliki keluaran yang sesuai dengan setiap transisi. Ada dua jenis mesin keadaan hingga yang menghasilkan keluaran -

  • Mesin Mealy
  • Mesin Moore

Mesin Mealy

Mesin Mealy adalah FSM yang keluarannya bergantung pada kondisi saat ini serta masukan saat ini.

Ini dapat dijelaskan dengan 6 tupel (Q, ∑, O, δ, X, q 0 ) di mana -

  • Q adalah sekumpulan negara yang terbatas.

  • adalah seperangkat simbol terbatas yang disebut alfabet masukan.

  • O adalah seperangkat simbol terbatas yang disebut alfabet keluaran.

  • δ adalah fungsi transisi masukan di mana δ: Q × ∑ → Q

  • X adalah fungsi transisi keluaran di mana X: Q × ∑ → O

  • q0adalah keadaan awal dari mana input diproses (q 0 ∈ Q).

Tabel status Mesin Mealy ditunjukkan di bawah ini -

Keadaan sekarang Negara bagian selanjutnya
masukan = 0 masukan = 1
Negara Keluaran Negara Keluaran
→ 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

Diagram status Mesin Mealy di atas adalah -

Mesin Moore

Mesin Moore adalah FSM yang keluarannya hanya bergantung pada kondisi saat ini.

Mesin Moore dapat dijelaskan dengan 6 tupel (Q, ∑, O, δ, X, q 0 ) di mana -

  • Q adalah sekumpulan negara yang terbatas.

  • adalah seperangkat simbol terbatas yang disebut alfabet masukan.

  • O adalah seperangkat simbol terbatas yang disebut alfabet keluaran.

  • δ adalah fungsi transisi masukan di mana δ: Q × ∑ → Q

  • X adalah fungsi transisi keluaran di mana X: Q → O

  • q0adalah keadaan awal dari mana input diproses (q 0 ∈ Q).

Tabel status Mesin Moore ditunjukkan di bawah ini -

Keadaan sekarang Status Berikutnya Keluaran
Masukan = 0 Masukan = 1
→ a b c x 2
b b d x 1
c c d x 2
d d d x 3

Diagram status dari Mesin Moore di atas adalah -

Mesin Mealy vs Mesin Moore

Tabel berikut menyoroti poin-poin yang membedakan Mesin Mealy dari Mesin Moore.

Mesin Mealy Mesin Moore
Keluaran bergantung pada keadaan sekarang dan masukan saat ini Keluaran hanya bergantung pada keadaan saat ini.
Secara umum, ia memiliki status yang lebih sedikit daripada Moore Machine. Secara umum, ia memiliki lebih banyak status daripada Mealy Machine.
Nilai fungsi keluaran merupakan fungsi transisi dan perubahan, ketika logika masukan pada keadaan sekarang dilakukan. Nilai fungsi keluaran adalah fungsi dari keadaan saat ini dan perubahan di tepi jam, setiap kali terjadi perubahan keadaan.
Mesin mealy bereaksi lebih cepat terhadap input. Mereka umumnya bereaksi dalam siklus jam yang sama. Di mesin Moore, lebih banyak logika diperlukan untuk memecahkan kode output yang menghasilkan lebih banyak penundaan sirkuit. Mereka umumnya bereaksi satu siklus jam kemudian.

Mesin Moore ke Mesin Mealy

Algoritma 4

Input - Mesin Moore

Output - Mesin Mealy

Step 1 - Ambil format tabel transisi Mealy Machine kosong.

Step 2 - Salin semua status transisi Mesin Moore ke dalam format tabel ini.

Step 3- Periksa status saat ini dan output yang sesuai di tabel status Mesin Moore; jika untuk output Q i status adalah m, salin ke kolom output dari tabel status Mealy Machine di mana pun Q i muncul di status berikutnya.

Contoh

Mari kita pertimbangkan mesin Moore berikut -

Keadaan Sekarang Status Berikutnya Keluaran
a = 0 a = 1
→ a d b 1
b Sebuah d 0
c c c 0
d b Sebuah 1

Sekarang kami menerapkan Algoritma 4 untuk mengubahnya menjadi Mesin Mealy.

Step 1 & 2 -

Keadaan Sekarang Status Berikutnya
a = 0 a = 1
Negara Keluaran Negara Keluaran
→ a d b
b Sebuah d
c c c
d b Sebuah

Step 3 -

Keadaan Sekarang Status Berikutnya
a = 0 a = 1
Negara Keluaran Negara Keluaran
=> a d 1 b 0
b Sebuah 1 d 1
c c 0 c 0
d b 0 Sebuah 1

Mesin Mealy ke Mesin Moore

Algoritma 5

Input - Mesin Mealy

Output - Mesin Moore

Step 1- Hitung jumlah output yang berbeda untuk setiap status (Q i ) yang tersedia dalam tabel status mesin Mealy.

Step 2- Jika semua keluaran Qi sama, salin status Q i . Jika ia memiliki n keluaran yang berbeda, bagi Q i menjadi n status sebagai Q di manan = 0, 1, 2 .......

Step 3 - Jika keluaran dari keadaan awal adalah 1, masukkan keadaan awal baru di awal yang memberikan 0 keluaran.

Contoh

Mari kita simak Mesin Mealy berikut -

Keadaan Sekarang Status Berikutnya
a = 0 a = 1
Status Berikutnya Keluaran Status Berikutnya Keluaran
→ a d 0 b 1
b Sebuah 1 d 0
c c 1 c 0
d b 0 Sebuah 1

Di sini, status 'a' dan 'd' hanya memberikan 1 dan 0 output, jadi kami mempertahankan status 'a' dan 'd'. Tetapi status 'b' dan 'c' menghasilkan keluaran yang berbeda (1 dan 0). Jadi, kami membagib ke b0, b1 dan c ke c0, c1.

Keadaan Sekarang Status Berikutnya Keluaran
a = 0 a = 1
→ a d b 1 1
b 0 Sebuah d 0
b 1 Sebuah d 1
c 0 c 1 C 0 0
c 1 c 1 C 0 1
d b 0 Sebuah 0