Kumpulan Contoh Soal Mesin Moore dari Dasar hingga Lanjutan

Dalam dunia teori bahasa dan otomata, kita mengenal adanya Finite State Machine (FSM) yang memiliki output. Salah satu model yang paling fundamental adalah Mesin Moore. Berbeda dengan saudaranya, Mesin Mealy, Mesin Moore memiliki karakteristik unik di mana output ditentukan sepenuhnya oleh state saat ini, bukan oleh input yang diterima pada state tersebut.

Artikel ini akan mengupas tuntas kumpulan contoh soal Mesin Moore, mulai dari konsep paling sederhana hingga penerapan logika yang lebih kompleks, untuk membantu Anda menguasai materi ini dengan cepat dan akurat.

Baca juga: Tips Cepat Mengerjakan Soal Numerasi PKN SMP Disertai Contoh Soal

Memahami Fondasi Mesin Moore

Sebelum masuk ke contoh soal, kita perlu menyatukan persepsi tentang definisi formalnya. Mesin Moore didefinisikan dalam 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$, di mana:

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

Ciri khas utama yang perlu Anda ingat: Output dicetak tepat saat kita memasuki sebuah state. Jika sebuah mesin menerima string sepanjang $n$, maka output yang dihasilkan akan berjumlah $n+1$ karena adanya output dari state awal.

Level 1: Contoh Soal Dasar (Pengenalan Konsep)

Soal-soal pada level ini bertujuan untuk melatih ketelitian Anda dalam menelusuri transisi dan mencatat output yang muncul pada setiap langkah.

Soal 1: Penelusuran Output Sederhana

Diketahui sebuah Mesin Moore dengan komponen sebagai berikut:

• State: $\{q_0, q_1, q_2\}$
• Input: $\{0, 1\}$
• Output: $\{a, b\}$
• Transisi:
  • $\delta(q_0, 0) = q_1, \delta(q_0, 1) = q_0$
  • $\delta(q_1, 0) = q_1, \delta(q_1, 1) = q_2$
  • $\delta(q_2, 0) = q_2, \delta(q_2, 1) = q_0$
• Output State: $\lambda(q_0) = a, \lambda(q_1) = b, \lambda(q_2) = a$

Pertanyaan: Tentukan output jika diberikan input 0110!

Pembahasan:

Mari kita telusuri langkah demi langkah:

1. Mulai di $q_0$: Output pertama adalah $\lambda(q_0) = \mathbf{a}$.
2. Input 0: Dari $q_0$ ke $q_1$. Output: $\lambda(q_1) = \mathbf{b}$.
3. Input 1: Dari $q_1$ ke $q_2$. Output: $\lambda(q_2) = \mathbf{a}$.
4. Input 1: Dari $q_2$ ke $q_0$. Output: $\lambda(q_0) = \mathbf{a}$.
5. Input 0: Dari $q_0$ ke $q_1$. Output: $\lambda(q_1) = \mathbf{b}$.

Hasil Akhir: ababb

Soal 2: Membuat Diagram dari Tabel Transisi

Seringkali dalam ujian, soal diberikan dalam bentuk tabel. Cobalah visualisasikan mesin berikut:

Pertanyaan: Buatlah diagram transisinya!

Tips Pengerjaan:

Gambarlah tiga lingkaran untuk S0, S1, dan S2. Di dalam lingkaran tersebut, tuliskan nilai outputnya (misalnya: S0/0). Kemudian tarik panah sesuai dengan kolom input 0 dan 1. Perhatikan bahwa setiap state harus memiliki tepat dua panah keluar (satu untuk input 0 dan satu untuk input 1).

Level 2: Menengah (Logika Deteksi String)

Mesin Moore sering digunakan untuk mendeteksi kemunculan pola tertentu dalam sebuah deret input.

Soal 3: Pendeteksi Pola “101”

Buatlah rancangan Mesin Moore yang mengeluarkan output ‘1’ jika string “101” terdeteksi, dan ‘0’ untuk kondisi lainnya.

Logika Berpikir:

1. State awal ($q_0$): Belum ada pola yang ditemukan. Output 0.
2. State $q_1$: Berhasil menemukan ‘1’. Output 0.
3. State $q_2$: Berhasil menemukan ’10’. Output 0.
4. State $q_3$: Berhasil menemukan ‘101’. Output 1.

Tabel Transisi:

• Di $q_0$, jika input 1, pindah ke $q_1$. Jika 0, tetap di $q_0$.
• Di $q_1$, jika input 0, pindah ke $q_2$. Jika 1, tetap di $q_1$.
• Di $q_2$, jika input 1, pindah ke $q_3$. Jika 0, kembali ke $q_0$.
• Di $q_3$, jika input 0, pindah ke $q_2$ (karena membentuk pola “10”). Jika 1, kembali ke $q_1$.

Soal 4: Sisa Hasil Bagi (Modulo)

Rancanglah Mesin Moore yang menerima input biner dan mengeluarkan output sisa hasil bagi angka tersebut dengan 3 (Modulo 3).

Pembahasan:

Angka biner dibaca dari kiri ke kanan. Misal angka biner $x$. Jika kita menambah bit $b$ di belakang, maka nilai barunya menjadi $2x + b$.

• Jika $x \equiv 0 \pmod 3$, maka $2x+0 \equiv 0$ dan $2x+1 \equiv 1$.
• Jika $x \equiv 1 \pmod 3$, maka $2x+0 \equiv 2$ dan $2x+1 \equiv 3 \equiv 0$.
• Jika $x \equiv 2 \pmod 3$, maka $2x+0 \equiv 4 \equiv 1$ dan $2x+1 \equiv 5 \equiv 2$.

Maka kita butuh 3 state:

• $q_0$ (Sisa 0): Output 0.
• $q_1$ (Sisa 1): Output 1.
• $q_2$ (Sisa 2): Output 2.

Transisinya mengikuti logika perhitungan di atas. Misalnya, dari $q_1$ (Sisa 1) jika diberi input 0, maka akan menuju $q_2$.

Level 3: Lanjutan (Konversi dan Optimalisasi)

Pada tahap ini, Anda ditantang untuk menghubungkan Mesin Moore dengan model otomata lainnya.

Soal 5: Konversi Mesin Mealy ke Mesin Moore

Konversi adalah topik yang sangat sering muncul dalam ujian universitas. Diketahui Mesin Mealy dengan satu state $A$, jika input 0 outputnya $x$, jika input 1 outputnya $y$.

Langkah Konversi:

1. Identifikasi setiap state di Mesin Mealy.
2. Lihat output yang masuk ke state tersebut. Jika sebuah state di Mealy menerima transisi dengan output yang berbeda-beda, state tersebut harus dipecah di Mesin Moore.
3. Misal State $B$ di Mealy menerima input yang menghasilkan output ‘0’ dan input lain menghasilkan output ‘1’. Maka di Mesin Moore kita buat $B_0$ dan $B_1$.

Contoh Kasus:

Diberikan transisi Mealy: $\delta(q_0, a) = (q_1, 0)$ dan $\delta(q_2, a) = (q_1, 1)$.

Di Mesin Moore, state $q_1$ harus dipecah menjadi $q_{1-0}$ (output 0) dan $q_{1-1}$ (output 1). Semua transisi yang menuju $q_1$ dengan output 0 diarahkan ke $q_{1-0}$, dan sebaliknya.

Soal 6: Kompleksitas Desain Sistem Nyata

Rancanglah Mesin Moore untuk mengontrol pintu otomatis. Pintu memiliki sensor berat (input 1 jika ada orang, 0 jika tidak). Output adalah status motor pintu (1 untuk Terbuka, 0 untuk Tertutup). Pintu harus tetap terbuka selama 1 siklus tambahan setelah orang tersebut pergi.

Analisis State:

• $S_{close}$: Pintu tertutup, tidak ada orang. Output 0.
• $S_{open}$: Ada orang, pintu terbuka. Output 1.
• $S_{wait}$: Orang baru saja pergi, pintu tetap terbuka (delay). Output 1.

Transisi:

• $S_{close}$ + input 1 $\to S_{open}$.
• $S_{open}$ + input 1 $\to S_{open}$.
• $S_{open}$ + input 0 $\to S_{wait}$.
• $S_{wait}$ + input 1 $\to S_{open}$.
• $S_{wait}$ + input 0 $\to S_{close}$.

Tips Menghadapi Ujian Mesin Moore

1. Cek Panjang Output: Selalu ingat bahwa jika inputnya adalah “ABAB”, maka output Mesin Moore harus memiliki 5 karakter. Karakter pertama adalah output dari state awal sebelum input pertama diproses.
2. Gambarkan Tabel Dulu: Sebelum menggambar lingkaran dan panah yang berantakan, buatlah tabel transisi. Ini meminimalisir kesalahan logika.
3. Perhatikan State Awal: Pastikan panah “Start” menunjuk ke state awal yang benar. Seringkali mahasiswa lupa memberikan output pada state awal ini.
4. Uji dengan String Ekstrim: Ujilah rancangan Anda dengan string kosong, string yang sangat pendek, atau string yang memiliki pola berulang untuk memastikan tidak ada deadlock atau kesalahan logika.

Perbedaan Utama: Moore vs Mealy (Tabel Perbandingan)

Untuk memperdalam pemahaman, perhatikan tabel berikut yang sering menjadi bahan pertanyaan teori:

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 perancangan logika digital dan teori otomata. Dengan memahami bahwa output terikat pada state, Anda bisa merancang berbagai sistem mulai dari pendeteksi pola sederhana hingga pengontrol sistem fisik yang kompleks.

Kunci utama dalam menguasai Mesin Moore adalah latihan yang konsisten. Cobalah untuk memodifikasi contoh-contoh soal di atas, misalnya dengan mengubah pola yang dicari atau mengubah jumlah sisa hasil bagi pada soal modulo. Semakin sering Anda mencoba membangun transisinya, semakin tajam insting logika Anda.

Semoga kumpulan contoh soal ini bermanfaat untuk studi Anda. Teruslah bereksperimen dengan diagram dan tabel transisi untuk memperkuat pemahaman visual dan analitis Anda.

Penulis: Aripin