Dalam studi Teori Bahasa dan Automata (TBA), memahami Finite State Machine (FSM) adalah fondasi krusial. Salah satu jenis FSM yang paling sering dipelajari selain Mesin Mealy adalah Mesin Moore. Bagi mahasiswa Informatika, menguasai Mesin Moore bukan sekadar untuk lulus ujian, melainkan untuk memahami bagaimana logika perangkat keras (seperti traffic light controller) dan protokol komunikasi bekerja di tingkat rendah.
Baca juga: 10 Contoh Soal Mesin Moore Lengkap dengan Pembahasan Mudah Dipahami
Apa Itu Mesin Moore?
Mesin Moore adalah tipe Finite State Transducer di mana nilai output ditentukan semata-mata oleh state saat ini, tanpa dipengaruhi oleh input secara langsung pada saat itu. Karakteristik utamanya adalah output berasosiasi dengan state. Jika sebuah Mesin Moore menerima input dengan panjang $n$, maka panjang output yang dihasilkan adalah $n+1$, karena adanya output awal dari start state sebelum input pertama diproses.
Secara formal, Mesin Moore didefinisikan dengan 6 tupel $(Q, \Sigma, \Delta, \delta, \lambda, q_0)$:
- $Q$: Himpunan hingga state.
- $\Sigma$: Alfabet input.
- $\Delta$: Alfabet output.
- $\delta$: Fungsi transisi ($Q \times \Sigma \to Q$).
- $\lambda$: Fungsi output ($Q \to \Delta$).
- $q_0$: Initial state.
Perbedaan Signifikan: Mesin Moore vs. Mesin Mealy
Mahasiswa sering kali tertukar antara keduanya. Kunci pengingatnya adalah:
- Moore: Output ada di dalam lingkaran (state). “More” (Moore) lambat karena harus masuk ke state dulu baru keluar output.
- Mealy: Output ada di transisi (panah). Mealy cenderung lebih cepat bereaksi terhadap input.
Karena output Moore bergantung pada state, jumlah state pada Mesin Moore biasanya lebih banyak dibandingkan Mesin Mealy untuk menyelesaikan persoalan yang sama.
Strategi Mengerjakan Soal Mesin Moore
Untuk menjawab soal-soal ujian atau tugas, gunakan langkah-langkah sistematis berikut:
- Analisis Alfabet: Tentukan apa inputnya (misal: 0,1 atau a,b) dan apa output yang diinginkan (misal: Sisa bagi, Deteksi Pola).
- Tentukan State: Definisikan makna dari setiap state. Misalnya, $q_0$ sebagai sisa 0, $q_1$ sebagai sisa 1.
- Gambar Diagram Transisi: Hubungkan antar state berdasarkan input.
- Sematkan Output: Tuliskan output di dalam setiap lingkaran state.
- Uji dengan String: Lakukan trace pada string contoh untuk memastikan output sesuai.
Kumpulan Contoh Soal Mesin Moore dan Pembahasannya
Contoh 1: Modulo 3 Bilangan Biner
Soal: Buatlah Mesin Moore yang menerima input bilangan biner dan mengeluarkan output sisa pembagian bilangan tersebut dengan 3 (Modulo 3).
Analisis:
- Input $\Sigma = \{0, 1\}$
- Output $\Delta = \{0, 1, 2\}$
- State: Kita butuh 3 state untuk mewakili sisa 0, sisa 1, dan sisa 2.
Jawaban:
- State $q_0$: Sisa 0 (Sekaligus start state). Output: 0.
- State $q_1$: Sisa 1. Output: 1.
- State $q_2$: Sisa 2. Output: 2.
Logika Transisi:
Ingat aturan biner: Jika angka biner $x$ diikuti input $b$, maka nilai barunya adalah $2x + b$.
- Dari $q_0$ (nilai 0):
- Input 0 $\to 2(0)+0 = 0$ (Tetap di $q_0$)
- Input 1 $\to 2(0)+1 = 1$ (Ke $q_1$)
- Dari $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$)
- Dari $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$)
Tabel Transisi:
| Present State | Input 0 | Input 1 | Output (ฮป) |
| $q_0$ | $q_0$ | $q_1$ | 0 |
| $q_1$ | $q_2$ | $q_0$ | 1 |
| $q_2$ | $q_1$ | $q_2$ | 2 |
Contoh 2: Deteksi Pola String “101”
Soal: Rancanglah Mesin Moore yang mengeluarkan output ‘Y’ jika input mengandung substring “101”, dan ‘T’ jika tidak.
Analisis:
Mesin Moore mendeteksi pola di akhir. Karena kita mencari panjang 3 (“101”), kita butuh beberapa state transisi.
Jawaban:
- $q_0$: State awal (belum ada pola). Output: T.
- $q_1$: Menemukan “1”. Output: T.
- $q_2$: Menemukan “10”. Output: T.
- $q_3$: Menemukan “101” (Pola lengkap). Output: Y.
Transisi:
- $q_0$ dengan input 1 ke $q_1$.
- $q_1$ dengan input 0 ke $q_2$.
- $q_2$ dengan input 1 ke $q_3$ (Output Y muncul di sini).
- Jika di $q_3$ dapat input 0, maka kembali ke pola “10”, yaitu ke $q_2$.
- Jika di $q_3$ dapat input 1, maka kembali ke pola “1”, yaitu ke $q_1$.
Contoh 3: Komplemen Satu (1’s Complement)
Soal: Buatlah Mesin Moore untuk menghasilkan komplemen satu dari sebuah bilangan biner.
Analisis:
Komplemen satu berarti mengubah 0 menjadi 1, dan 1 menjadi 0. Namun, tantangan Mesin Moore adalah ia selalu mengeluarkan output pertama sebelum membaca input.
Jawaban:
Kita memerlukan state yang merepresentasikan apa yang baru saja dibaca.
- $q_{start}$: State awal. Output: Sembarang (biasanya $\epsilon$ atau tanda mulai).
- $q_{zero}$: Terakhir baca 0. Output: 1.
- $q_{one}$: Terakhir baca 1. Output: 0.
Tabel Transisi:
| State | Input 0 | Input 1 | Output |
| $q_{start}$ | $q_{zero}$ | $q_{one}$ | – |
| $q_{zero}$ | $q_{zero}$ | $q_{one}$ | 1 |
| $q_{one}$ | $q_{zero}$ | $q_{one}$ | 0 |
Contoh 4: Menghitung Kemunculan Substring “AA”
Soal: Diberikan $\Sigma = \{A, B\}$, buatlah Mesin Moore yang menghitung setiap kali urutan “AA” muncul. Gunakan output 1 untuk mendeteksi dan 0 untuk lainnya.
Jawaban:
- $q_0$: State awal / baru saja baca B. Output 0.
- $q_1$: Baru saja baca satu A. Output 0.
- $q_2$: Baru saja baca AA. Output 1.
Transisi:
- $q_0$ jika input A $\to q_1$, jika B $\to q_0$.
- $q_1$ jika input A $\to q_2$ (Deteksi!), jika B $\to q_0$.
- $q_2$ jika input A $\to q_2$ (Karena “AAA” mengandung dua “AA” yang tumpang tindih), jika B $\to q_0$.
Uji String “BAAA”:
- Mulai di $q_0 \to$ Output 0.
- Input B: tetap di $q_0 \to$ Output 0.
- Input A: ke $q_1 \to$ Output 0.
- Input A: ke $q_2 \to$ Output 1.
- Input A: ke $q_2 \to$ Output 1.
- Total Output: 00011 (Dua angka 1 di akhir menandakan ada dua pola “AA” yang terdeteksi secara beruntun).
Tips Sukses Ujian Teori Bahasa Automata
- Perhatikan Jumlah Output: Selalu ingat bahwa jika input $011$ (panjang 3), hasil trace Mesin Moore harus memiliki 4 karakter. Jika dosen Anda meminta hasil yang presisi, tanyakan apakah output dari initial state harus diabaikan atau dicantumkan.
- Gunakan Tabel dan Diagram: Saat menjawab, sajikan kedua bentuk (diagram lingkaran dan tabel transisi). Ini menunjukkan pemahaman yang komprehensif.
- Cek Kondisi “Deadlock”: Pastikan setiap state memiliki transisi untuk setiap simbol di alfabet input ($\Sigma$). Jika alfabetnya $\{0, 1\}$, maka setiap lingkaran wajib punya dua panah keluar.
- Sederhanakan State: Jangan membuat state terlalu banyak. Jika dua state memiliki transisi yang sama untuk input yang sama dan menghasilkan output yang sama, mereka bisa digabung (Ekuivalensi State).
Kesimpulan
Mesin Moore adalah alat yang kuat untuk memodelkan sistem digital di mana output stabil pada state tertentu. Dengan memahami hubungan antara state dan output, serta berlatih soal-soal seperti Modulo dan Deteksi Pola, Anda akan lebih siap menghadapi mata kuliah Teori Bahasa dan Automata maupun Perancangan Sistem Digital.
Ingatlah bahwa kunci utama belajar automata adalah visualisasi. Jangan ragu untuk menggambar coret-coretan diagram sebelum memindahkannya ke lembar jawaban ujian.
Penulis: Aripin
Post Comment