Contoh Soal Mesin Moore Paling Sering Keluar di Ujian Otomata: Panduan Lengkap dan Pembahasan

Memahami Teori Bahasa dan Automata (TBA) seringkali menjadi tantangan tersendiri bagi mahasiswa teknik informatika atau ilmu komputer. Salah satu materi yang menjadi “langganan” muncul dalam ujian adalah Finite State Machine (FSM) dengan Output, khususnya Mesin Moore.

Artikel ini akan membedah secara mendalam mengenai konsep, struktur, hingga kumpulan contoh soal Mesin Moore yang paling sering keluar di ujian, lengkap dengan langkah-langkah penyelesaiannya yang sistematis.

Baca juga: Panduan Mudah Menguasai Soal Past Future Contoh dan Jawaban Lengkap

Apa Itu Mesin Moore?

Sebelum masuk ke contoh soal, kita perlu menyamakan persepsi. Mesin Moore adalah tipe Finite State Transducer di mana nilai output ditentukan semata-mata oleh state saat ini. Berbeda dengan temannya, Mesin Mealy, yang outputnya bergantung pada kombinasi state dan simbol input.

Secara formal, Mesin Moore didefinisikan dengan 6-tuple $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$:

• $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.

Karakteristik Khas Mesin Moore dalam Soal Ujian

Dalam ujian, dosen biasanya memberikan soal yang menguji ketelitian Anda pada poin-poin berikut:

1. Panjang Output: Jika panjang input adalah $n$, maka panjang output pada Mesin Moore selalu $n+1$. Hal ini karena state awal ($q_0$) sudah menghasilkan output sebelum ada input yang dibaca.
2. Penulisan Output: Output biasanya ditulis di dalam lingkaran state bersama dengan nama state tersebut (misal: $q_0/0$).

Kumpulan Contoh Soal Mesin Moore dan Pembahasannya

Berikut adalah variasi soal yang paling sering muncul, mulai dari tingkat dasar hingga analisis logika.

Soal 1: Konversi Deskripsi Verbal ke Diagram State

Pertanyaan:

Buatlah diagram Mesin Moore yang menerima input biner $\{0, 1\}$ dan memberikan output “A” jika urutan input diakhiri dengan ’10’, dan output “B” untuk kondisi lainnya.

Pembahasan:

Langkah pertama adalah menentukan state yang dibutuhkan:

• $q_0$: State awal (belum menerima apa-apa). Output: B.
• $q_1$: Sudah menerima input ‘1’. Output: B.
• $q_2$: Sudah menerima urutan ’10’. Output: A.

Tabel Transisi dan Output:

Logika Kerja:

Jika kita memasukkan input 10, maka jalurnya adalah:

• Mulai di $q_0$ (Output B)
• Input 1 $\to$ pindah ke $q_1$ (Output B)
• Input 0 $\to$ pindah ke $q_2$ (Output A)Total Output: BBA. (Ingat aturan $n+1$).

Soal 2: Menghitung Sisa Bagi (Modulus) dengan Mesin Moore

Ini adalah tipe soal “maut” yang sering keluar di ujian tengah atau akhir semester.

Pertanyaan:

Rancanglah Mesin Moore yang menerima input biner dan mengeluarkan sisa pembagian bilangan biner tersebut dengan 3 (Modlo 3).

Pembahasan:

Dalam soal sisa bagi $n$, kita membutuhkan tepat $n$ buah state. Untuk modulo 3, pilih state $q_0, q_1, q_2$ yang masing-masing merepresentasikan sisa bagi 0, 1, dan 2.

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

Fungsi Transisi:

Ingat rumus biner: Jika bilangan $x$ diberi tambahan bit $b$ di belakangnya, maka nilai barunya adalah $2x + b$.

• Jika di $q_0$ (nilai 0), input 0 $\to 2(0)+0 = 0$ (ke $q_0$). Input 1 $\to 2(0)+1 = 1$ (ke $q_1$).
• Jika di $q_1$ (nilai 1), input 0 $\to 2(1)+0 = 2$ (ke $q_2$). Input 1 $\to 2(1)+1 = 3 \equiv 0 \pmod 3$ (ke $q_0$).
• Jika di $q_2$ (nilai 2), input 0 $\to 2(2)+0 = 4 \equiv 1 \pmod 3$ (ke $q_1$). Input 1 $\to 2(2)+1 = 5 \equiv 2 \pmod 3$ (ke $q_2$).

Soal 3: Melacak Output dari Jalur State (Tracing)

Pertanyaan:

Diberikan sebuah Mesin Moore dengan $Q = \{q_0, q_1\}$, $\Sigma = \{a, b\}$, $\Delta = \{0, 1\}$.

Fungsi transisi:

$\delta(q_0, a) = q_1, \delta(q_0, b) = q_0$

$\delta(q_1, a) = q_1, \delta(q_1, b) = q_0$

Fungsi output:

$\lambda(q_0) = 0, \lambda(q_1) = 1$

Berapakah output jika diberikan input “ababa”?

Pembahasan:

Mari kita telusuri satu per satu:

1. State Awal: $q_0$. Output: 0.
2. Input ‘a’: $\delta(q_0, a) = q_1$. Output: 1.
3. Input ‘b’: $\delta(q_1, b) = q_0$. Output: 0.
4. Input ‘a’: $\delta(q_0, a) = q_1$. Output: 1.
5. Input ‘b’: $\delta(q_1, b) = q_0$. Output: 0.
6. Input ‘a’: $\delta(q_0, a) = q_1$. Output: 1.

Hasil Akhir: 010101.

Catatan: Input ada 5 karakter, output ada 6 karakter. Jika jawaban Anda hanya 5 karakter, dipastikan salah.

Tips Menjawab Soal Mesin Moore Agar Mendapat Nilai A

Berdasarkan pengalaman koreksi ujian, berikut kesalahan umum yang harus Anda hindari:

1. Lupa Output State Awal

Banyak mahasiswa langsung memproses input pertama. Padahal, Mesin Moore langsung mengeluarkan output begitu “listrik” dinyalakan (saat berada di $q_0$). Selalu tulis output $q_0$ di depan rangkaian jawaban Anda.

2. Tertukar dengan Mesin Mealy

Jika dalam soal diminta Mesin Moore, pastikan output berada di dalam lingkaran state. Jika Anda meletakkan output di garis panah (transisi), itu adalah Mesin Mealy, dan poin Anda bisa dipotong drastis.

3. Tidak Melengkapi Tabel Transisi

Seringkali mahasiswa hanya menggambar diagram. Padahal, tabel transisi membantu dosen melihat logika Anda jika gambar diagramnya sedikit berantakan. Gunakan format tabel yang rapi.

Perbedaan Signifikan Moore vs Mealy (Sering Ditanyakan di Teori)

Dalam soal ujian esai, terkadang muncul pertanyaan: “Apa keuntungan menggunakan Mesin Moore dibandingkan Mesin Mealy?”

Latihan Mandiri: Uji Kemampuan Anda

Cobalah kerjakan soal berikut untuk menguji pemahaman Anda:

Rancang Mesin Moore yang menghitung jumlah kemunculan substring “11” dalam sebuah string biner. Misalnya input “111”, maka output harus menunjukkan deteksi di posisi yang sesuai.

(Petunjuk: Gunakan state untuk melacak apakah Anda baru saja melihat angka ‘1’ atau sudah melihat dua angka ‘1’ berturut-turut).

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

Kesimpulan

Mesin Moore adalah konsep dasar yang krusial dalam perancangan sirkuit digital dan pemrosesan bahasa alami. Kunci utama dalam mengerjakan soalnya adalah ketelitian dalam menghitung panjang output dan pemahaman mendalam terhadap transisi state.

Dengan menguasai tipe soal modulo dan pelacakan output (tracing), Anda sudah mengamankan setidaknya 70% nilai pada bab Finite State Machine di ujian Otomata.

Penulis: Aripin