Chapter 4: Deterministic Finite Automata (DFA) dan Non-Deterministic Finite Automata (NFA) - Academics

Konsep & Pembahasan Terperinci

1. Determinisme (DFA) vs Non-Determinisme (NFA)

DFA (Deterministic Finite Automaton):
- Untuk setiap state $q$ dan simbol $a \in \Sigma$ , transisi $\delta(q, a)$ menghasilkan tepat satu state berikutnya.
- Alur eksekusi bersifat deterministik: string input yang sama pada mesin yang sama pasti menghasilkan urutan lintasan yang identik dan dapat diprediksi.
NFA (Non-Deterministic Finite Automaton):
- Untuk suatu state $q$ dan simbol $a$ , transisi $\delta(q, a)$ menghasilkan himpunan state (bisa kosong $\emptyset$ , satu state, atau beberapa state sekaligus).
- Eksekusi tidak membentuk garis lurus tunggal, melainkan pohon pelacakan eksekusi (tree of execution).

2. Tiga Cara Memandang Komputasi NFA

Bagaimana kita mengonseptualisasikan cara NFA bekerja ketika menghadapi banyak cabang pilihan?

NFA adalah "Penebak Sempurna": Asumsikan mesin selalu memilih cabang transisi yang membawanya ke state Final (jika memang ada jalur sukses).
NFA Menggandakan Diri (Cloning): Setiap kali menjumpai persimpangan dengan $k$ cabang, mesin menduplikasi dirinya menjadi $k$ proses independen.
Komputasi Paralel: Mesin menelusuri seluruh kemungkinan konfigurasi state secara serentak (concurrently).

Kriteria Keputusan:

Diterima (Accept): Jika terdapat paling sedikit satu cabang di pohon eksekusi yang berhasil mencapai state Final setelah seluruh string input habis dibaca.
Ditolak (Reject): Jika seluruh cabang yang mungkin mengalami stuck (tidak memiliki transisi lanjutan) atau berakhir di state yang bukan Final.

3. Definisi Formal NFA

NFA didefinisikan sebagai 5-tuple:

N = (Q, \Sigma, \delta, q_0, F)

Struktur tuple sama dengan DFA, kecuali pada fungsi transisi $\delta$ :

\delta : Q \times \Sigma \longrightarrow 2^Q

Di mana $2^Q$ adalah powerset (himpunan kuasa) dari $Q$ , yaitu himpunan seluruh himpunan bagian dari $Q$ . Nilai $\delta(q, a)$ adalah himpunan $\{p_1, p_2, \dots\} \subseteq Q$ .

Studi Kasus: NFA Bahasa Berakhiran '01' & Subset Construction

1. Desain NFA

Bahasa: $L = \{w \in \{0, 1\}^* \mid w \text{ berakhiran } 01\}$
Himpunan State: $Q = \{q_0, q_1, q_2\}$ , State Awal: $q_0$ , State Final: $F = \{q_2\}$
Tabel Transisi NFA:

State	Input $0$	Input $1$
$\to q_0$	$\{q_0, q_1\}$	$\{q_0\}$
$q_1$	$\emptyset$	$\{q_2\}$
$*q_2$	$\emptyset$	$\emptyset$

Ide non-deterministik: Di state $q_0$ , mesin bebas "menebak" apakah simbol 0 yang dibacanya adalah awal dari akhiran 01 (pindah ke $q_1$ ), atau sekadar bagian dari prefiks awal (tetap di $q_0$ ).

2. Algoritma Subset Construction (Konversi NFA ke DFA)

DFA yang ekuivalen dibangun dengan menjadikan himpunan bagian state NFA sebagai state tunggal pada DFA.

State Awal DFA:

A = [q_0]

Transisi dari State $A = [q_0]$ :
- Baca 0: $\delta(q_0, 0) = \{q_0, q_1\} \implies \text{Bentuk state baru } B = [q_0, q_1]$
- Baca 1: $\delta(q_0, 1) = \{q_0\} = A$
Transisi dari State $B = [q_0, q_1]$ :
- Baca 0: $\delta(q_0, 0) \cup \delta(q_1, 0) = \{q_0, q_1\} \cup \emptyset = \{q_0, q_1\} = B$
- Baca 1: $\delta(q_0, 1) \cup \delta(q_1, 1) = \{q_0\} \cup \{q_2\} = \{q_0, q_2\} \implies \text{Bentuk state baru } C = [q_0, q_2]$
Transisi dari State $C = [q_0, q_2]$ :
- Baca 0: $\delta(q_0, 0) \cup \delta(q_2, 0) = \{q_0, q_1\} \cup \emptyset = \{q_0, q_1\} = B$
- Baca 1: $\delta(q_0, 1) \cup \delta(q_2, 1) = \{q_0\} \cup \emptyset = \{q_0\} = A$
Menentukan State Final DFA:

Setiap state komposit yang memuat state final NFA ( $q_2$ ) menjadi state Final DFA. Karena hanya $C = [q_0, q_2]$ yang memuat $q_2$ , maka $F_{\text{DFA}} = \{C\}$ .

Tabel Transisi DFA Hasil Konversi:

State Komposit	Label State DFA	Input $0$	Input $1$	Status Final?
$[q_0]$	$\to A$	$B$	$A$	Bukan Final
$[q_0, q_1]$	$B$	$B$	$C$	Bukan Final
$[q_0, q_2]$	$*C$	$B$	$A$	Final (Accepting)

Perbandingan Konsep

Parameter	Deterministic Finite Automata (DFA)	Non-Deterministic Finite Automata (NFA)
Fungsi Transisi	$\delta : Q \times \Sigma \to Q$ (Tepat 1 state)	$\delta : Q \times \Sigma \to 2^Q$ (Himpunan subset state)
Bentuk Eksekusi	Lintasan sekuensial tunggal	Pohon percabangan (Execution Tree)
Syarat Terima	Lintasan berakhir di state final	Minimal 1 cabang berakhir di state final
Kemudahan Desain	Cenderung kompleks & kaku	Sangat intuitif untuk mencocokkan pola
Implementasi Komputer	Sangat cepat & efisien ( $O(n)$ )	Perlu simulasi subset / backtracking
Daya Komputasi	Setara (Bahasa Reguler)	Setara (Bahasa Reguler)

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Apa yang membedakan fungsi transisi $\delta$ pada DFA dengan NFA secara matematis?

Soal 1.2

Jelaskan 3 cara memandang dan menginterpretasikan cara kerja komputasi pada NFA.

Pembahasan/Jawaban

1.1 Pada DFA, $\delta$ memetakan ke sebuah state tunggal ( $\delta : Q \times \Sigma \to Q$ ), sedangkan pada NFA, $\delta$ memetakan ke himpunan bagian dari $Q$ ( $\delta : Q \times \Sigma \to 2^Q$ ).

1.2 Tiga cara memandang komputasi NFA:

NFA selalu mengambil tebakan yang benar
NFA menggandakan diri (copy) pada setiap percabangan
NFA menjelajahi seluruh kemungkinan secara paralel

Level 2 - Intermediate

Soal 2.1

Diberikan NFA berakhiran 01 di atas. Lacak eksekusi string $w = 001$ menggunakan pohon eksekusi dan tunjukkan mengapa string ini diterima.

Pembahasan/Jawaban

Mulai di $q_0$ .
Baca 0: Cabang terbagi menjadi $\{q_0, q_1\}$ .
Baca 0:
- Dari $q_0$ dengan 0 $\to$ cabang menjadi $\{q_0, q_1\}$ .
- Dari $q_1$ dengan 0 $\to \emptyset$ (stuck).
- Total cabang aktif saat ini: $\{q_0, q_1\}$ .
Baca 1:
- Dari $q_0$ dengan 1 $\to \{q_0\}$ .
- Dari $q_1$ dengan 1 $\to \{q_2\}$ .
- Total cabang aktif akhir: $\{q_0, q_2\}$ .

Karena salah satu cabang berakhir di $q_2 \in F$ , string $001$ diterima (Accepted).

Level 3 - Advanced

Soal 3.1

Jika suatu NFA memiliki $n$ buah state, berapa jumlah maksimum state yang mungkin terbentuk pada DFA hasil konversi Subset Construction? Mengapa?

Pembahasan/Jawaban

Jumlah maksimum state pada DFA adalah $2^n$ state. Hal ini karena setiap state pada DFA merepresentasikan sebuah himpunan bagian (subset) dari himpunan state NFA. Powerset dari sebuah himpunan berkardinalitas $n$ memiliki tepat $2^n$ elemen. Meskipun dalam praktiknya banyak subset yang tidak dapat dicapai (unreachable), batas atas teoretisnya adalah eksponensial ( $2^n$ ).

Exam Cheat Sheet

Pemetaan NFA: $\delta : Q \times \Sigma \to 2^Q$ .
Syarat Terima NFA: $\hat{\delta}(q_0, w) \cap F \ne \emptyset$ .
Ekuivalensi: $L(M_{\text{DFA}}) = L(M_{\text{NFA}})$ . NFA tidak lebih sakti dari DFA dalam mengenali bahasa, keduanya persis mencakup Regular Languages.
Tujuan NFA $\to$ DFA: NFA untuk spesifikasi manusia (pattern matching, lexer), DFA untuk eksekusi deterministik cepat pada mesin.
Prinsip Subset Construction: Gabungkan state-state yang dapat dicapai secara bersamaan menjadi satu kesatuan state komposit.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 4 telah membuktikan bahwa non-determinisme memberikan fleksibilitas tanpa menambah batas komputasi. Pada bab berikutnya, Chapter 5: NFA dengan ε-move, kita akan melengkapi NFA dengan kemampuan transisi spontan tanpa membaca simbol masukan.