10 Contoh Soal Mesin Moore Lengkap dengan Pembahasan Mudah Dipahami

artikel contoh soal 10 Contoh Soal Mesin Moore Lengkap dengan Pembahasan Mudah Dipahami January 27, 2026 0 Comments

Daftar Isi

Apa Itu Mesin Moore?
10 Contoh Soal Mesin Moore dan Pembahasannya
Perbedaan Utama: Moore vs Mealy
Tips Mengerjakan Soal Mesin Moore
Kesimpulan

Dalam dunia informatika dan teori bahasa formal, memahami State Machine adalah fondasi utama. Salah satu yang paling populer adalah Mesin Moore (Moore Machine). Berbeda dengan saudaranya, Mesin Mealy, Mesin Moore memiliki ciri khas di mana output ditentukan sepenuhnya oleh state saat ini, bukan oleh input.

Artikel ini akan menyajikan 10 contoh soal Mesin Moore yang dirancang khusus untuk membantu mahasiswa atau pegiat IT memahami konsep ini secara mendalam namun tetap sederhana.

Baca juga: Bank Soal Intelegensi Umum CPNS Terbaru 2026 Lengkap dengan Kunci Jawaban

Apa Itu Mesin Moore?

Sebelum masuk ke latihan soal, mari kita segarkan ingatan sejenak. Secara matematis, Mesin Moore didefinisikan dalam 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$:

$Q$: Himpunan state.
$\Sigma$: Alfabet input.
$\Delta$: Alfabet output.
$\delta$: Fungsi transisi ($Q \times \Sigma \rightarrow Q$).
$\lambda$: Fungsi output ($Q \rightarrow \Delta$).
$q_0$: State awal.

Kunci utamanya: Output ada di dalam lingkaran state. Jika Anda masuk ke State A, maka output yang dihasilkan akan selalu sama selama Anda berada di sana, apa pun input yang membawa Anda ke sana.

10 Contoh Soal Mesin Moore dan Pembahasannya

Soal 1: Deteksi Sisa Bagi (Modulus 3)

Buatlah Mesin Moore yang menerima input biner dan mengeluarkan output berupa sisa bagi angka biner tersebut jika dibagi 3.

Pembahasan:

Logika: Sisa bagi angka jika dibagi 3 bisa berupa 0, 1, atau 2. Maka kita butuh 3 state: $q_0$ (sisa 0), $q_1$ (sisa 1), dan $q_2$ (sisa 2).
State & Output:
- $q_0$ memiliki output 0.
- $q_1$ memiliki output 1.
- $q_2$ memiliki output 2.
Transisi:
- Dari $q_0$, jika input 0 tetap di $q_0$, jika input 1 ke $q_1$.
- Dari $q_1$, jika input 0 ke $q_2$, jika input 1 ke $q_0$.
- Dari $q_2$, jika input 0 ke $q_1$, jika input 1 tetap di $q_2$.

Soal 2: Menghitung Kemunculan Substring “11”

Rancang Mesin Moore yang mengeluarkan output ‘Y’ (Yes) setiap kali urutan input “11” terdeteksi, dan ‘N’ (No) untuk lainnya.

Pembahasan:

State: Kita butuh state untuk “Belum ada 1”, “Sudah ada satu angka 1”, dan “Sudah lengkap 11”.
Alur:
- $S_0$ (Start/Belum ada 1): Output N.
- $S_1$ (Ketemu 1 pertama): Output N.
- $S_2$ (Ketemu 1 kedua): Output Y.
Jika di $S_2$ menerima input 1 lagi, ia tetap di $S_2$ karena pola “11” masih terpenuhi di akhir rangkaian.

Soal 3: Konversi Biner ke Komplemen Satu

Buatlah mesin yang mengubah input biner menjadi komplemen satunya (0 jadi 1, 1 jadi 0).

Pembahasan:

Ini adalah kasus Mesin Moore yang sangat sederhana.

State $A$: Output 0 (untuk input 1).
State $B$: Output 1 (untuk input 0).
Setiap input 0 akan mengarahkan ke State $B$, dan setiap input 1 mengarahkan ke State $A$.

Soal 4: Detektor Paritas Genap

Mesin Moore yang mengeluarkan output 1 jika jumlah angka ‘1’ yang masuk adalah genap, dan 0 jika ganjil.

Pembahasan:

State $q_{even}$ (Awal): Output 1 (karena nol dianggap genap).
State $q_{odd}$: Output 0.
Transisi: Input ‘1’ akan memindahkan state dari genap ke ganjil atau sebaliknya. Input ‘0’ tidak mengubah jumlah ‘1’, jadi state tetap.

Soal 5: Mesin Penjual Otomatis (Vending Machine) Sederhana

Mesin hanya menerima koin 500 dan 1000. Harga minuman adalah 1500. Output ‘1’ keluar jika uang sudah cukup.

Pembahasan:

$q_0$: Saldo 0 (Output 0).
$q_1$: Saldo 500 (Output 0).
$q_2$: Saldo 1000 (Output 0).
$q_3$: Saldo 1500 (Output 1).
Setiap input menambah posisi state hingga mencapai $q_3$.

Soal 6: Deteksi Akhiran “01”

Buat Mesin Moore yang mendeteksi apakah string biner diakhiri dengan “01”.

Pembahasan:

$S_0$: State netral.
$S_1$: State setelah mendapat ‘0’.
$S_2$: State setelah mendapat ‘0’ diikuti ‘1’.
Output $S_2$ adalah 1, sedangkan $S_0$ dan $S_1$ adalah 0. Penting untuk diingat bahwa Mesin Moore akan selalu menghasilkan output awal ($n+1$ output untuk $n$ input).

Soal 7: Pembagi Frekuensi (Flip-Flop T)

Buat mesin yang mengubah output setiap kali menerima input ‘1’.

Pembahasan:

State $A$ (Output 0): Jika input 1 pindah ke $B$. Jika 0 tetap di $A$.
State $B$ (Output 1): Jika input 1 pindah ke $A$. Jika 0 tetap di $B$.Ini adalah implementasi dasar dari counter atau pembagi frekuensi dalam sirkuit digital.

Soal 8: Deteksi Substring “ABC”

Gunakan alfabet $\{A, B, C\}$. Berikan output ‘X’ saat “ABC” terbaca.

Pembahasan:

Dibutuhkan 4 state:
1. Start (Output -)
2. Found A (Output -)
3. Found AB (Output -)
4. Found ABC (Output X)
Jika di tengah jalan input tidak sesuai (misal di Found AB malah dapat ‘A’), transisi harus kembali ke state yang relevan (Found A).

Soal 9: Mesin Moore untuk Incrementer Biner

Mesin yang menambah angka biner dengan 1 (proses dilakukan dari LSB ke MSB).

Pembahasan:

Ini cukup kompleks karena melibatkan carry.

State Carry: Menambahkan 1. Jika input 1, output 0 dan tetap bawa carry. Jika input 0, output 1 dan pindah ke state No Carry.
State No Carry: Hanya menyalin input ke output (0 jadi 0, 1 jadi 1).

Soal 10: Pengenalan Pola “1010”

Mesin Moore yang mendeteksi pola tumpang tindih (overlapping) “1010”.

Pembahasan:

State 0: Start.
State 1: Ketemu “1”.
State 2: Ketemu “10”.
State 3: Ketemu “101”.
State 4: Ketemu “1010” (Output 1).
Setelah State 4, jika input “1”, ia kembali ke State 3 karena akhiran “101” sudah terbentuk dari “1010” + “1”.

Perbedaan Utama: Moore vs Mealy

Seringkali dalam ujian, Anda diminta membandingkan keduanya. Berikut ringkasannya:

Fitur	Mesin Moore	Mesin Mealy
Penentu Output	Hanya State saat ini	State saat ini & Input
Jumlah State	Biasanya lebih banyak	Biasanya lebih sedikit
Kecepatan Respon	Lebih lambat (menunggu clock)	Lebih cepat (bereaksi langsung)
Penempatan Output	Di dalam State	Pada transisi (panah)

Tips Mengerjakan Soal Mesin Moore

Tentukan Output Dulu: Identifikasi kapan output harus berubah. Ini akan menentukan jumlah state minimal Anda.
Gambar Diagram Transisi: Jangan langsung membuat tabel. Gambar lingkaran dan panah untuk memvisualisasikan alur logika.
Cek Kondisi “Macet”: Pastikan setiap state memiliki transisi untuk setiap kemungkinan alfabet input. Jangan ada state yang “bingung” harus ke mana saat menerima input tertentu.
Verifikasi dengan Contoh String: Ujilah diagram Anda dengan string pendek (misal: “1101”) dan lihat apakah outputnya sesuai harapan. Ingat, jumlah output Mesin Moore selalu $L+1$ di mana $L$ adalah panjang string input.

Baca juga: Universitas Teknokrat Indonesia Kenalkan Metaverse & AI di SMKN 3 Kotabumi, Dorong Siswa Manfaatkan Teknologi untuk Karier

Kesimpulan

Mesin Moore adalah alat yang sangat kuat dalam desain logika digital dan teori komputasi. Dengan memahami bahwa output terikat pada state, kita bisa membangun sistem yang lebih stabil dan mudah diprediksi. Latihan di atas mencakup dasar-dasar yang sering muncul dalam ujian akademis maupun seleksi teknis.

Penulis: Aripin