Belajar Mesin Moore: Panduan Lengkap Contoh Soal, Tabel Transisi, dan Output

Dunia informatika dan otomata sering kali terasa abstrak bagi banyak orang. Namun, di balik kecanggihan perangkat lunak yang kita gunakan sehari-hari, terdapat konsep fundamental yang mengatur bagaimana sebuah sistem merespons input. Salah satu konsep paling krusial dalam teori bahasa dan otomata adalah Mesin Moore (Moore Machine).

Artikel ini akan mengupas tuntas apa itu Mesin Moore, perbedaannya dengan Mesin Mealy, cara kerja tabel transisi, hingga contoh soal yang mendalam agar Anda benar-benar menguasai materi ini.

Baca juga: 10 Contoh Soal Mesin Moore Lengkap dengan Pembahasan Mudah Dipahami

Apa Itu Mesin Moore?

Mesin Moore adalah tipe Finite State Machine (FSM) atau mesin status terbatas di mana nilai output ditentukan semata-mata oleh status (state) saat ini. Berbeda dengan kerabat dekatnya, Mesin Mealy, yang outputnya dipengaruhi oleh status dan input, Mesin Moore jauh lebih sederhana secara struktur karena outputnya “menempel” pada setiap status.

Dalam terminologi matematika, Mesin Moore didefinisikan sebagai 6-tuple $(S, S_0, \Sigma, \Lambda, T, G)$:

• $S$: Himpunan status yang terbatas (finite set of states).
• $S_0$: Status awal (initial state).
• $\Sigma$: Alfabet input yang terbatas (input alphabet).
• $\Lambda$: Alfabet output yang terbatas (output alphabet).
• $T$: Fungsi transisi yang memetakan status dan input ke status berikutnya ($S \times \Sigma \to S$).
• $G$: Fungsi output yang memetakan status ke alfabet output ($S \to \Lambda$).

Kunci utama yang perlu diingat: Output pada Mesin Moore terjadi saat kita berada di sebuah state, bukan saat terjadi transisi.

Perbedaan Mesin Moore dan Mesin Mealy

Sebelum masuk ke contoh soal, penting untuk memahami posisi Mesin Moore dalam spektrum mesin otomata.

1. Output: Pada Mesin Moore, output terkait dengan state. Pada Mesin Mealy, output terkait dengan transisi (panah).
2. Jumlah Status: Biasanya, untuk menjalankan fungsi yang sama, Mesin Moore membutuhkan jumlah status yang lebih banyak atau sama dengan Mesin Mealy.
3. Respon: Mesin Moore cenderung lebih aman digunakan dalam desain sirkuit digital karena outputnya tetap stabil selama berada di state tersebut, tidak langsung berubah seketika saat input masuk.

Memahami Tabel Transisi dan Tabel Output

Untuk merepresentasikan cara kerja Mesin Moore, kita menggunakan dua alat utama: Diagram Transisi dan Tabel Transisi/Output.

Tabel transisi membantu kita melihat ke mana sebuah sistem akan berpindah jika diberikan input tertentu. Karena output pada Mesin Moore hanya bergantung pada status, kita bisa menggabungkan kolom output langsung di samping kolom status saat ini.

Contoh Soal 1: Deteksi Sisa Bagi (Modulus)

Mari kita mulai dengan contoh klasik. Buatlah Mesin Moore yang menerima input biner dan mengeluarkan output sisa bagi angka tersebut jika dibagi 3.

Langkah 1: Tentukan Status

• $q_0$: Sisa bagi 0 (Status awal)
• $q_1$: Sisa bagi 1
• $q_2$: Sisa bagi 2

Langkah 2: Tentukan Output

• Output di $q_0 = 0$
• Output di $q_1 = 1$
• Output di $q_2 = 2$

Langkah 3: Analisis Transisi

Dalam biner, jika kita menambah angka ‘0’ di belakang, nilainya menjadi $2n$. Jika menambah ‘1’, nilainya menjadi $2n + 1$.

• Dari $q_0$ (0 mod 3):
  • Input 0: $2(0) = 0 \to$ tetap di $q_0$.
  • Input 1: $2(0) + 1 = 1 \to$ pindah ke $q_1$.
• Dari $q_1$ (1 mod 3):
  • Input 0: $2(1) = 2 \to$ pindah ke $q_2$.
  • Input 1: $2(1) + 1 = 3 \equiv 0 \pmod 3 \to$ pindah ke $q_0$.
• Dari $q_2$ (2 mod 3):
  • Input 0: $2(2) = 4 \equiv 1 \pmod 3 \to$ pindah ke $q_1$.
  • Input 1: $2(2) + 1 = 5 \equiv 2 \pmod 3 \to$ tetap di $q_2$.

Tabel Transisi Mesin Moore Modulo 3:

Contoh Soal 2: Deteksi Pola Tertentu

Buatlah Mesin Moore yang mengeluarkan output ‘Y’ (Yes) jika menemukan urutan input “11” dan ‘N’ (No) jika belum menemukannya.

Langkah 1: Identifikasi State

• $S_0$: Keadaan awal, belum ada angka 1 yang masuk. (Output: N)
• $S_1$: Sudah ada satu angka ‘1’ yang masuk. (Output: N)
• $S_2$: Sudah ditemukan pola “11”. (Output: Y)

Langkah 2: Alur Transisi

1. Di $S_0$: Jika input 0, tetap di $S_0$. Jika input 1, pindah ke $S_1$.
2. Di $S_1$: Jika input 0, balik ke $S_0$. Jika input 1, pindah ke $S_2$ (Pola tercapai).
3. Di $S_2$: Jika input 1, tetap di $S_2$. Jika input 0, balik ke $S_0$.

Tabel Transisi dan Output:

Cara Membaca Output Mesin Moore

Ada satu hal unik yang sering membingungkan pemula: Panjang Output.

Pada Mesin Moore, karena status awal ($S_0$) sudah memiliki output bahkan sebelum ada input yang masuk, maka jika panjang input adalah $n$, panjang output akan menjadi $n + 1$.

Misalnya pada Contoh Soal 2 di atas, jika kita memasukkan input: 110

1. Awal: State $S_0 \to$ Output: N
2. Input 1: Ke $S_1 \to$ Output: N
3. Input 1: Ke $S_2 \to$ Output: Y
4. Input 0: Ke $S_0 \to$ Output: NTotal Output: NNYN (4 karakter output untuk 3 karakter input).

Implementasi Mesin Moore dalam Kehidupan Nyata

Mungkin Anda bertanya, “Untuk apa saya belajar ini?”. Mesin Moore adalah fondasi dari:

1. Desain CPU: Control unit dalam prosesor sering kali dirancang menggunakan prinsip FSM.
2. Lampu Lalu Lintas: Perubahan warna lampu bergantung pada status saat ini (misal: Merah) dan timer (input).
3. Vending Machine: Mesin minuman menghitung jumlah koin yang masuk (input) dan berpindah status hingga mencapai jumlah yang cukup untuk mengeluarkan produk (output).
4. Game Development: AI musuh yang memiliki status “Patroli”, “Mengejar”, dan “Menyerang” bekerja dengan prinsip Moore atau Mealy.

Tips Mengerjakan Soal Mesin Moore

1. Gambar Diagram Dulu: Jangan langsung membuat tabel. Visualisasikan lingkaran (state) dan panah (transisi). Tuliskan output di dalam lingkaran bersama nama state-nya.
2. Cek Semua Input: Pastikan setiap state memiliki panah keluar untuk semua kemungkinan alfabet input. Jika inputnya {0, 1}, maka setiap lingkaran harus punya dua panah keluar.
3. Verifikasi Output Awal: Jangan lupa menyertakan output dari status awal sebelum input pertama diproses.

Baca juga: Universitas Teknokrat Indonesia Peringkat Pertama Kampus Swasta Terbaik di Lampung Versi Webometrics 2026

Kesimpulan

Belajar Mesin Moore adalah langkah awal yang sangat baik untuk memahami logika komputasi. Dengan memfokuskan output pada status, Mesin Moore memberikan model yang stabil dan mudah diprediksi dalam perancangan sistem digital.

Penulis: Aripin