Chapter 6: Finite Automata dengan Output (Mesin Moore dan Mesin Mealy) - Academics

Konsep & Pembahasan Terperinci

1. Dua Perbedaan Fundamental Moore vs Mealy

Parameter	Mesin Moore	Mesin Mealy
Penempatan Output	Berada di dalam setiap state (asosiasi state murni)	Berada di setiap cabang transisi (asosiasi pasangan state & input)
Panjang Output	$\|w_{\text{out}}\| = \|w_{\text{in}}\| + 1$	$\|w_{\text{out}}\| = \|w_{\text{in}}\|$
Pemicu Output	Bergantung hanya pada state saat ini	Bergantung pada state saat ini DAN simbol input yang dibaca
Output Awal	Mengeluarkan output bawaan state awal $q_0$ sebelum membaca simbol pertama	Tidak mengeluarkan output sebelum membaca simbol pertama

2. Definisi Formal Mesin Moore dan Mealy

A. Mesin Moore

Didefinisikan sebagai 5-tuple:

M_o = (Q, \Sigma, \tau, \delta, q_0)

$Q$ : Himpunan berhingga state.
$\Sigma$ : Alfabet simbol masukan (input), contoh: $\{a, b\}$ .
$\tau$ : Alfabet simbol keluaran (output), contoh: $\{0, 1\}$ .
$\delta$ : Fungsi transisi state: $Q \times \Sigma \to Q$ .
$q_0$ : State awal ( $q_0 \in Q$ ).

(Fungsi output $\lambda$ memetakan state langsung ke output: $\lambda : Q \to \tau$ ).

B. Mesin Mealy

Didefinisikan sebagai 5-tuple:

M_e = (Q, \Sigma, \tau, \delta, q_0)

Komponen himpunan sama, namun fungsi output menghasilkan simbol keluaran bersamaan dengan transisi:

\lambda : Q \times \Sigma \longrightarrow \tau

Studi Kasus & Tracing Lengkap

1. Mesin Moore 1 (Detektor Pola '101')

State: $\{S_0, S_1, S_2, S_3\}$ , State Awal: $q_0 = S_0$
Alfabet Input: $\Sigma = \{a, b\}$ , Alfabet Output: $\tau = \{0, 1\}$

Tabel Transisi dan Output Moore 1:

State ( $Q$ )	Transisi Input $a$	Transisi Input $b$	Output ( $\tau$ )
$\to S_0$	$S_1$	$S_3$	1
$S_1$	$S_3$	$S_1$	0
$S_2$	$S_0$	$S_3$	0
$S_3$	$S_3$	$S_2$	1

Tracing String Masukan $w = \text{abaab}$ :

Kondisi Awal: Berada di state $S_0$ $\implies$ Langsung menghasilkan output 1.
Baca simbol a: $S_0 \xrightarrow{a} S_1$ $\implies$ State $S_1$ menghasilkan output 0.
Baca simbol b: $S_1 \xrightarrow{b} S_1$ $\implies$ State $S_1$ menghasilkan output 0.
Baca simbol a: $S_1 \xrightarrow{a} S_3$ $\implies$ State $S_3$ menghasilkan output 1.
Baca simbol a: $S_3 \xrightarrow{a} S_3$ $\implies$ State $S_3$ menghasilkan output 1.
Baca simbol b: $S_3 \xrightarrow{b} S_2$ $\implies$ State $S_2$ menghasilkan output 0.

Rangkuman Alur State: $S_0 \xrightarrow{a} S_1 \xrightarrow{b} S_1 \xrightarrow{a} S_3 \xrightarrow{a} S_3 \xrightarrow{b} S_2$
Total Output: 100110 (Panjang input $= 5$ , Panjang output $= 6$ ).

2. Mesin Moore 2 (Penghitung Residu Modulo Biner)

Tabel Transisi dan Output Moore 2:

State ( $Q$ )	Transisi Input $a$	Transisi Input $b$	Output ( $\tau$ )
$\to S_0$	$S_1$	$S_0$	0
$S_1$	$S_2$	$S_0$	0
$S_2$	$S_2$	$S_3$	0
$S_3$	$S_1$	$S_0$	1

Analisis Semantik Mesin Moore 2: Perhatikan bahwa satu-satunya state dengan output 1 adalah $S_3$ . State $S_3$ hanya dapat dicapai melalui urutan lintasan: $S_0 \xrightarrow{a} S_1 \xrightarrow{a} S_2 \xrightarrow{b} S_3$ . Artinya mesin ini mendeteksi pola substring aab!

Tracing Masukan Panjang $w = \text{abaabbaaabaab}$ :

Output yang dihasilkan: 00000100001001 (Panjang input $= 13$ , Panjang output $= 14$ ).
Simbol 1 muncul tepat saat akhiran aab selesai dibaca.

3. Mesin Mealy (Transduser Komplemen Biner)

Tabel Transisi dan Output Mealy:

State ( $Q$ )	Input $a$ : Next State	Input $a$ : Output	Input $b$ : Next State	Input $b$ : Output
$\to S_0$	$S_1$	0	$S_3$	0
$S_1$	$S_3$	1	$S_2$	1
$S_2$	$S_3$	0	$S_3$	1
$S_3$	$S_3$	1	$S_0$	1

Tracing String Masukan $w = \text{aabba}$ :

Berada di $S_0$ , baca a $\implies$ Pindah ke $S_1$ , keluarkan 0.
Berada di $S_1$ , baca a $\implies$ Pindah ke $S_3$ , keluarkan 1.
Berada di $S_3$ , baca b $\implies$ Pindah ke $S_0$ , keluarkan 1.
Berada di $S_0$ , baca b $\implies$ Pindah ke $S_3$ , keluarkan 0.
Berada di $S_3$ , baca a $\implies$ Pindah ke $S_3$ , keluarkan 1.

Total Output: 01101 (Panjang input $= 5$ , Panjang output $= 5$ ).

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Jika sebuah string masukan memiliki panjang $n = 10$ , tentukan panjang string keluaran pada Mesin Moore dan Mesin Mealy.

Soal 1.2

Di manakah posisi simbol output diletakkan pada diagram transisi Mesin Mealy?

Pembahasan/Jawaban

1.1 Pada Mesin Moore, panjang output $= n + 1 = 11$ . Pada Mesin Mealy, panjang output $= n = 10$ .

1.2 Pada Mesin Mealy, output diletakkan pada busur/jalur transisi dengan format notasi input / output (misalnya a / 1).

Level 2 - Intermediate

Soal 2.1

Lakukan tracing pada Mesin Mealy di atas untuk string masukan $w = \text{bababb}$ , dan buktikan apakah output yang dihasilkan adalah 011011 secara tepat.

Pembahasan/Jawaban

$S_0 \xrightarrow{b} S_3$ , output: 0
$S_3 \xrightarrow{a} S_3$ , output: 1
$S_3 \xrightarrow{b} S_0$ , output: 1
$S_0 \xrightarrow{a} S_1$ , output: 0
$S_1 \xrightarrow{b} S_2$ , output: 1
$S_2 \xrightarrow{b} S_3$ , output: 1

Urutan output gabungan: 011011. Terbukti menghasilkan deretan output yang tepat.

Level 3 - Advanced

Soal 3.1

Mengapa Mesin Moore selalu menghasilkan satu simbol output lebih banyak daripada panjang string masukan?

Pembahasan/Jawaban

Karena pada Mesin Moore, nilai output terikat langsung pada state, bukan pada transisi. Begitu mesin diaktifkan (power on), mesin sudah langsung menempati state awal $q_0$ dan seketika itu pula mengeluarkan output bawaan dari $q_0$ (pada saat $t=0$ ), bahkan sebelum satu pun simbol dari string masukan dibaca. Kemudian, setiap kali satu simbol input dibaca, mesin berpindah state dan mengeluarkan satu output baru. Total output menjadi $1 + n$ .

Exam Cheat Sheet

Rumus Panjang Output:

\text{Moore} = |w| + 1 \qquad \text{Mealy} = |w|

Letak Output:
- Moore: Di dalam lingkaran state ( $S_i / \text{out}$ ).
- Mealy: Di panah transisi ( $\text{in} / \text{out}$ ).
Tuple 5 Komponen: $M = (Q, \Sigma, \tau, \delta, q_0)$ dengan $\tau$ sebagai alfabet output.
Pola Pembacaan: Moore mengeluarkan output state awal di awal eksekusi; Mealy baru mengeluarkan output saat transisi terjadi.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 6 mengalihkan fokus kita ke mesin transduser ber-output. Pada bab selanjutnya, Chapter 7: Minimisasi DFA, kita akan mempelajari algoritma matematis untuk mereduksi jumlah state pada DFA agar diperoleh mesin yang paling efisien.