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 |