LAPORAN KONVERSI MESIN MOORE DAN MESIN MEALY
OTOMATA DAN TEORI BAHASA
Disusun Oleh :
Achmad Yuszril Oiszy (A11.1027.10209)
Nurul Arifin (A11.2017.10210)
Tri Mega Widyawan (A11.2017.10224)
Aprilia Dhammashanti (A11.2017.10236)
Moch. Zidni Ilman (A11.2017.10615)
Kelompok A11.4410
PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS ILMU KOMPUTER
UNIVERSITAS DIAN NUSWANTORO
TAHUN 2019
MESIN MOORE
Mesin moore adalah finite-state machine yang nilai outputnya ditentukan berdasarkan statenya.
Mesin Moore dinamai Edward F. Moore, yang mempresentasikan konsep itu dalam sebuah makalah tahun 1956, "Gedanken-experiments on Sequential Machines"
Diagram Mesin Moore atau Diagram Moore adalah diagram yang menghubungkan nilai output dengan masing-masing state.
Mesin moore ditetapkan ke dalam 6 tuple yang terdiri dari:
- Himpunan State (S)
- State awal (S0)
- Himpunan input (∑)
- Himpunan output (ꓥ)
- Fungsi Transisi (T)
- Fungsi output (G)
MESIN MEALY
Mesin Mealy adalah finite-state machine yang nilai outputnya ditentukan oleh state dan inputnya.
Mesin Mealy adalah deterministic finite-state transducer, untuk setiap keadaan dan masukan, paling banyak satu transisi dimungkinkan.
Diagram mesin mealy menghubungkan nilai output dengan masing-masing transisi.
Mesin moore ditetapkan ke dalam 6 tuple yang terdiri dari:
- Himpunan State (S)
- State awal (S0)
- Himpunan input (∑)
- Himpunan output (ꓥ)
- Fungsi Transisi (T)
- Fungsi output (G)
HUBUNGAN ANTARA MESIN MOORE DAN MESIN MEALY
Karena keduanya adalah sebuah finite-state machine, keduanya dapat digunakan untuk membaca bahasa regular.
Semua Mesin Moore setara dengan Mesin Mealy dengan state, transisi, dan output yang sama.
Namun, tidak semua Mesin Mealy dapat dikonversi menjadi Mesin Moore yang setara. Beberapa dapat dikonversi menjadi Mesin Moore yang hampir setara, dengan output yang bergeser dalam satu waktu.
Hal ini disebabkan oleh cara state dihubungkan dengan transisi untuk membentuk input dan output.
Perlu diketahui bahwa tidak semua lintasan sekuensial dapat diimplementasikan menggunakan Mesin Mealy, beberapa hanya bisa diimplementasikan menjadi mesin moore.
Perbedaannya adalah :
1. Pada Mesin Moore, setiap state dinyatakan sebagai nilai output
2. Pada Mesin Mealy, setiap transisi dinyatakan sebagai nilai output
Perbandingan Mesin Moore dan Mesin Mealy:
1. Mesin Mealy memiliki state yang lebih sedikit.
2. Mesin Moore lebih aman digunakan, karena:
- Output berubah pada satu siklus.
- Pada Mesin Mealy, perubahan input dapat langsung merubah output, hal ini
dapat menyebabkan 2 mesin yang terhubung menjadi tidak sinkron.
3. Mesin Mealy bereaksi lebih cepat pada input, karena:
- Bereaksi daam satu siklus
- Pada Mesin Moore, beberapa logika perlu diproses pada state untuk
menjadi output
KONVERSI MESIN MOORE KE MESIN MEALY
TEOREMA:
q Setiap mesin moore dapat diubah menjadi mesin mealy yang menghasilkan output yang sama
q Setiap panah yang menuju suatu state pada mesin moore akan menjadi panah dengan output sama dengan output state pada mesin mealy
Contoh :
Tentukan konversi mesin moore ke mesin mealy
JAWAB
Buat tabel transisinya dahulu
Present State
|
Next State
|
Output
| |
0
|
1
| ||
 -> q0 |  q3 |
q1
|
1
|
q1
|
q0
|
q3
|
0
|
q2
|
q2
|
q2
|  0 |
q3
 |
q1
|
q0
|
1
|
1. Pertama-tama ambil format table transisi mesin moore
2. Untuk mencari output kita lihat contoh pada q0 ke q3 adalah 1 (dan seterusnya)
3. Sehingga didapat hasil seperti dibawah ini
Present State
|
Next State
| |||
0
|
1
| |||
State
|
Output
|
State
|
Output
| |
->q0
|
q3
|
1
|
q1
|
0
|
q1
|
q0
|
1
|
q3
|
1
|
q2
|
q2
|
0
|
q2
|
0
|
q3
|
q1
|
0
|
q0
|
1
|
Sehingga diagram statenya menjadi :
KONVERSI MESIN MEALY KE MESIN MOORE
TEOREMA:
q Setiap mesin mealy dapat diubah menjadi mesin moore yang akan menghasilkan output yang sama.
q Jika panah yang masuk sebuah state memiliki input yang sama (pada mesin moore).
q Jika panah yang masuk sebuah state memiliki input yang berbeda (pada mesin moore).
q Jika panah yang masuk sebuah state memiliki input yang berbeda dan salah satunya adalah panah looping (pada mesin moore).
Contoh :
Tentukan konversi mesin mealy ke mesin moore
Present State
|
Next State
| |||
0
|
1
| |||
State
|
output
|
State
|
Output
| |
-> q0
|
q3
|
0
|
q1
|
1
|
q1
|
q0
|
1
|
q3
|
0
|
q2
|
q2
|
1
|
q2
|
0
|
q3
|
q1
|
0
|
q0
|
1
|
Jawab :
Mealy
Present State
|
Next State
| |||
0
|
1
| |||
State
|
output
|
State
|
Output
| |
-> q0
|
q3
|
0
|
q1
|
1
|
q1
|
q0
|
1
|
q3
|
0
|
q2
|
q2
|
1
|
q2
|
0
|
q3
|
q1
|
0
|
q0
|
1
|
moore
Present State
|
Next State
| |||
0
|
1
| |||
State
|
Output
|
State
|
Output
| |
-> q0
|
q3
|
0
|
q1
|
1
|
q10
|
q0
|
1
|
q3
|
0
|
q11
|
q0
|
1
|
q3
|
0
|
q20
|
q2
|
1
|
q2
|
0
|
q21
|
q2
|
1
|
q2
|
0
|
q3
|
q1
|
0
|
q0
|
1
|
q Cek state pada next state, jika output berbeda maka dibagi menjadi dua bagian.
1. Cek state q0, outputnya sama bernilai 0 maka tidak dibagi dua bagian
2. Cek state q1, outputnya bernilai 0 dan 1 maka dibagi dua bagian menjadi q00 dan q01
3. Cek state q2, outputnya bernilai 0 dan 1 maka dibagi dua bagian menjadi q00 dan q01
4. Untuk menentukan output pada moore kita harus cek next state pada tabel mealy
LATIHAN SOAL
1. Diketahui Mesin Moore tentukan mesin Mealy yang eqivalen
Jawab :
Moore
Present State
|
Next State
| |||
0
|
1
| |||
State
|
Output
|
State
|
Output
| |
B
|
A
|
0
|
B
|
1
|
mealy
Present State
|
0
|
1
|
Output
|
A
|
A
|
B
|
0
|
B
|
A
|
B
|
1
|
Diagram state menjadi :
2. Diketahui Mesin Mealy tentukan mesin Moore yang eqivalen
Jawab :
Mealy
Present State
|
Next State
| |||
a
|
b
| |||
state
|
output
|
state
|
Output
| |
->S0
|
S1
|
0
|
S30
|
0
|
S1
|
S31
|
1
|
S2
|
1
|
S2
|
S30
|
0
|
S31
|
1
|
S30
|
S31
|
1
|
S0
|
1
|
S31
|
S31
|
1
|
S0
|
1
|
Moore
Present State
|
Next State
| ||
a
|
b
|
Output
| |
->S0
|
S1
|
S30
|
1
|
S1
|
S31
|
S2
|
0
|
S2
|
S30
|
S31
|
1
|
S30
|
S31
|
S0
|
0
|
S31
|
S31
|
S0
|
1
|
Diagram statenya menjadi :
3. Diketahui Mesin Mealy tentukan mesin Moore yang eqivalen
Jawab :
Mealy
Present State
|
Next State
| |||
0
|
1
| |||
state
|
output
|
state
|
Output
| |
->A
|
A
|
0
|
B
|
1
|
B
|
C
|
2
|
A
|
0
|
C
|
B
|
1
|
C
|
2
|
Moore
Present State
|
Next State
|
Output
| |
0
|
1
| ||
->A
|
A
|
B
|
0
|
B
|
C
|
A
|
1
|
C
|
B
|
C
|
2
|
Sehingga diagram statenya menjadi :
4. Diketahui Mesin Moore tentukan mesin Mealy yang eqivalen
Jawab
Moore
Present State
|
Next State
|
Output
| |
a
|
b
| ||
->S0
|
S1
|
S0
|
0
|
S1
|
S2
|
S0
|
0
|
S2
|
S2
|
S3
|
0
|
S3
|
S1
|
S0
|
1
|
Present State
|
Next State
|
Output
| ||
a
|
b
| |||
state
|
output
|
state
|
output
| |
->S0
|
S1
|
0
|
S0
|
0
|
S1
|
S2
|
0
|
S0
|
0
|
S2
|
S2
|
0
|
S3
|
0
|
S3
|
S1
|
0
|
S0
|
1
|
Sehingga diagram statenya menjadi
5. Misalkan ada mesin Mealy, ubah ke dalam mesin Moore
Jawab
Mealy
Present State
|
Next State
| |||
0
|
1
| |||
state
|
output
|
state
|
Output
| |
->A
|
A
|
0
|
B
|
1
|
B
|
A
|
0
|
B
|
1
|
moore
Present State
|
Next State
|
Output
| |
0
|
1
| ||
->A
|
A
|
B
|
0
|
B
|
A
|
B
|
1
|
Sehingga diagram statenya menjadi
6. Diketahui Mesin Moore tentukan mesin Mealy yang eqivalen
Jawab
Present State
|
Next State
|
Output
| |
a
|
b
| ||
->S0
|
S1
|
S3
|
1
|
S1
|
S3
|
S1
|
0
|
S2
|
S0
|
S3
|
0
|
S3
|
S3
|
S2
|
1
|
mealy
Present State
|
Next State
| |||
0
|
1
| |||
state
|
output
|
state
|
Output
| |
->S0
|
S1
|
0
|
S3
|
1
|
S1
|
S3
|
1
|
S1
|
0
|
S2
|
S0
|
1
|
S3
|
1
|
S3
|
S3
|
1
|
S2
|
0
|
Sehingga diagram statenya menjadi :
1. Diketahui Mesin Moore tentukan mesin Maely yang eqivalen
Jawab :
Moore
Present State
|
Next State
|
Output
| |
a
|
b
| ||
->S0
|
S1
|
S3
|
1
|
S1
|
S3
|
S1
|
0
|
S2
|
S0
|
S3
|
0
|
S3
|
S3
|
S2
|
1
|
mealy
Present State
|
Next State
| |||
0
|
1
| |||
state
|
output
|
state
|
Output
| |
->S0
|
S1
|
0
|
S3
|
1
|
S1
|
S3
|
1
|
S1
|
0
|
S2
|
S0
|
1
|
S3
|
1
|
S3
|
S3
|
1
|
S2
|
0
|
Sehingga diagram statenya menjadi
7.
