Chapter 7: Minimisasi DFA dan Eliminasi State Redundan - Academics

Konsep & Pembahasan Terperinci

1. Tiga Kategori State Redundan

Unreachable State (Keadaan Tak Terjangkau):

State $p$ sedemikian hingga tidak ada string masukan $w \in \Sigma^*$ yang mampu membawa mesin dari state awal $q_0$ menuju $p$ ( $\forall w, \hat{\delta}(q_0, w) \ne p$ ). State ini dapat langsung dihapus beserta seluruh transisi keluarnya tanpa mengubah bahasa mesin.
Dead State (Keadaan Mati / Perangkap):

State non-final $p$ sedemikian hingga untuk seluruh input, transisi selalu berputar di dalam $p$ atau menuju state non-final lainnya, sehingga mustahil mencapai state final manapun.
Non-Distinguishable State (Keadaan Ekuivalen):

Dua state $p$ dan $q$ dikatakan saling ekuivalen ( $p \equiv q$ ) jika mesin tidak dapat membedakan keduanya dengan string penguji apapun:
- Jika dari $p$ membaca $w$ berakhir di Final, maka dari $q$ membaca $w$ harus berakhir di Final.
- Jika dari $p$ membaca $w$ berakhir di Non-Final, maka dari $q$ membaca $w$ harus berakhir di Non-Final.

2. Algoritma Partisi Kelas Ekuivalen Rekursif

Langkah 0:

Bagi $Q$ menjadi 2 grup besar (berdasarkan kemampuan membedakan string kosong $\epsilon$ berpanjang 0):

C_1 = F \quad \text{dan} \quad C_2 = Q - F

Langkah $k+1$ :

Untuk setiap grup yang berisi lebih dari 1 state, periksa transisi untuk setiap simbol masukan $a \in \Sigma$ .

Dua state $p$ dan $q$ tetap berada dalam kelas yang sama jika dan hanya jika untuk setiap $a \in \Sigma$ , $\delta(p, a)$ dan $\delta(q, a)$ berada pada kelas partisi yang sama di langkah sebelumnya.

Jika ada simbol yang memetakan ke kelas yang berbeda, grup tersebut harus dipecah (split).
Kondisi Berhenti:

Proses berhenti ketika pada suatu iterasi tidak ada satu pun kelas yang pecah lagi.

Studi Kasus Minimisasi State

Diberikan DFA dengan 6 state:

$Q = \{1, 2, 3, 4, 5, 6\}$ , Alfabet: $\Sigma = \{0, 1\}$ , State Awal: $1$, State Final: $F = \{3, 4\}$ .
Fungsi Transisi $\delta$ :
- State 1: $\delta(1, 0) = 2, \delta(1, 1) = 3$
- State 2: $\delta(2, 0) = 1, \delta(2, 1) = 4$
- State 3: $\delta(3, 0) = 3, \delta(3, 1) = 4$
- State 4: $\delta(4, 0) = 2, \delta(4, 1) = 3$
- State 5: $\delta(5, 0) = 5, \delta(5, 1) = 3$
- State 6: $\delta(6, 0) = 5, \delta(6, 1) = 3$

Pelacakan Partisi Langkah demi Langkah:

Langkah 0 (Partisi Final vs Non-Final):

C_1 = \{1, 2, 5, 6\} \quad (\text{Non-Final}), \qquad C_2 = \{3, 4\} \quad (\text{Final})

Langkah 1:

Cek $C_2 = \{3, 4\}$ pada input $0$:
- $\delta(3, 0) = 3 \in C_2$
- $\delta(4, 0) = 2 \in C_1$
Karena transisi input $0$ membawa ke kelas yang berbeda, maka $3$ dan $4$ harus dipisah!

Partisi baru:

C_1 = \{1, 2, 5, 6\}, \quad C_2 = \{3\}, \quad C_3 = \{4\}

Langkah 2:

Cek $C_1 = \{1, 2, 5, 6\}$ pada input $1$:
- $\delta(1, 1) = 3 \in C_2$
- $\delta(2, 1) = 4 \in C_3$
- $\delta(5, 1) = 3 \in C_2$
- $\delta(6, 1) = 3 \in C_2$
State 2 membawa ke $C_3$ , sedangkan 1, 5, 6 membawa ke $C_2$ . Maka state 2 memisahkan diri!

Partisi baru:

C_1 = \{1, 5, 6\}, \quad C_2 = \{2\}, \quad C_3 = \{3\}, \quad C_4 = \{4\}

Langkah 3:

Cek $C_1 = \{1, 5, 6\}$ pada input $0$:
- $\delta(1, 0) = 2 \in C_2$
- $\delta(5, 0) = 5 \in C_1$
- $\delta(6, 0) = 5 \in C_1$
State 1 membawa ke $C_2$ , sedangkan 5 dan 6 tetap di $C_1$ . Maka state 1 memisahkan diri!

Partisi baru:

C_1 = \{1\}, \quad C_2 = \{2\}, \quad C_3 = \{3\}, \quad C_4 = \{4\}, \quad C_5 = \{5, 6\}

Langkah 4:

Evaluasi ulang: Seluruh kelas berisi 1 state kecuali $C_5 = \{5, 6\}$ .
Cek $\{5, 6\}$ :
- Input $0$: $\delta(5, 0) = 5 \in C_5$ , $\delta(6, 0) = 5 \in C_5$ (Sama)
- Input $1$: $\delta(5, 1) = 3 \in C_3$ , $\delta(6, 1) = 3 \in C_3$ (Sama)
Tidak ada pemecahan baru. Algoritma Berhenti!

Observasi Eliminasi State Tak Terjangkau (Unreachable State):

Tinjau kelas $C_5 = \{5, 6\}$ :

Apakah ada panah dari state $\{1, 2, 3, 4\}$ yang menuju ke state 5 atau 6?
Dari graf transisi, tidak ada satu pun transisi yang masuk ke state 5 maupun 6.
Karena state awal adalah $1 \in C_1$ , maka kelas $C_5 = \{5, 6\}$ adalah Unreachable State dan dihilangkan sepenuhnya dari DFA minimal!

Hasil Akhir DFA Minimal $M'$ :

DFA minimal hanya memiliki 4 state:

$Q' = \{C_1, C_2, C_3, C_4\}$
State Awal: $C_1$ (memuat state awal 1)
State Final: $C_3$ dan $C_4$ (memuat state final 3 dan 4)

Tabel Transisi DFA Minimal:

State Minimal	Representasi State Lama	Input $0$	Input $1$	Status
$\to C_1$	$\{1\}$	$C_2$	$C_3$	State Awal
$C_2$	$\{2\}$	$C_1$	$C_4$	Biasa
$*C_3$	$\{3\}$	$C_3$	$C_4$	Final
$*C_4$	$\{4\}$	$C_2$	$C_3$	Final

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan 3 jenis keadaan (state) yang menjadi fokus eliminasi/penggabungan dalam minimisasi DFA.

Soal 1.2

Kapan algoritma partisi pembentukan kelas ekuivalen dihentikan?

Pembahasan/Jawaban

1.1 Tiga kategori state redundan:

Unreachable State (state tak terjangkau)
Dead State / Trap State (state buntu)
Non-distinguishable State (state-state yang ekuivalen)

1.2 Algoritma dihentikan ketika dalam satu putaran iterasi tidak ditemukan lagi kelas partisi baru yang terpecah (paling banyak dalam $|Q|$ langkah).

Level 2 - Intermediate

Soal 2.1

Pada Langkah 0 algoritma partisi di atas, mengapa himpunan state langsung dibagi menjadi dua kelas $C_1 = F$ dan $C_2 = Q - F$ ?

Pembahasan/Jawaban

Karena string kosong $\epsilon$ (panjang 0) langsung menjadi pembeda antara state final dan non-final. Untuk state $p \in F$ , $\hat{\delta}(p, \epsilon) = p \in F$ . Sedangkan untuk state $q \in Q - F$ , $\hat{\delta}(q, \epsilon) = q \notin F$ . Karena string $\epsilon$ membedakan keduanya, maka state final dan non-final pasti tidak ekuivalen ( $p \not\equiv_0 q$ ) dan wajib dipisahkan sejak awal.

Level 3 - Advanced

Soal 3.1

Mengapa kelas $C_5 = \{5, 6\}$ harus dieliminasi, padahal state 5 dan 6 saling ekuivalen satu sama lain?

Pembahasan/Jawaban

Meskipun state 5 dan 6 saling ekuivalen (memiliki transisi identik ke $C_5$ dan $C_3$ ), keduanya tidak memiliki lintasan masuk yang dapat dicapai dari state awal ( $q_0 = 1$ ). State yang tidak terjangkau (unreachable) tidak akan pernah dieksekusi oleh string masukan manapun yang sah. Oleh karena itu, keberadaannya mubazir dan wajib dieliminasi demi efisiensi memori.

Exam Cheat Sheet

Definisi Ekuivalensi: $p \equiv q \iff \forall w, (\hat{\delta}(p, w) \in F \iff \hat{\delta}(q, w) \in F)$ .
Langkah 0 Partisi: Selalu $C_1 = F$ dan $C_2 = Q - F$ .
Langkah $k+1$ : Pecah grup jika $\exists a \in \Sigma$ sedemikian hingga $\delta(p, a)$ dan $\delta(q, a)$ berada di partisi berbeda.
Pembersihan Akhir: Hapus kelas yang tidak memiliki jalur masuk dari state awal (unreachable).
Kompleksitas: Berhenti paling banyak dalam $|Q|$ langkah iterasi.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 7 melengkapi pembahasan mengenai representasi mesin otomatis. Pada bab berikutnya, Chapter 8: Regular Expression (Ekspresi Reguler), kita beralih ke notasi aljabar deklaratif untuk mendefinisikan bahasa reguler tanpa harus menggambar state.