Chapter 5: NFA dengan ε-move (ε-NFA) dan ε-Closure

Konsep & Pembahasan Terperinci

1. Hakikat dan Manfaat $\epsilon$-Move

• Apa itu $\epsilon$-move?

  Transisi $\epsilon$ adalah transisi "bebas biaya" (free transition): mesin dapat melompat dari state $p$ ke state $q$ tanpa membaca simbol apapun dari string input. Head pembaca pita input tidak bergeser.

• Mengapa Diperlukan Jika Tidak Menambah Daya Mesin?

  Dalam rekayasa sistem, kita sering kali ingin merancang modul-modul logika terpisah lalu menggabungkannya. Misalnya:

  • Modul $M_1$ mengenali bahasa $L_1$.

  • Modul $M_2$ mengenali bahasa $L_2$.

  Untuk membuat mesin yang mengenali gabungan bahasa $L_1 \cup L_2$, kita cukup membuat satu state awal baru $q_{\text{start}}$, lalu menarik transisi $\epsilon$ dari $q_{\text{start}}$ ke state awal $M_1$ dan ke state awal $M_2$. Inilah prinsip dasar modularitas automata.

---

2. Definisi Formal $\epsilon$-NFA

$\epsilon$-NFA didefinisikan sebagai 5-tuple:

Perbedaan tunggal dengan NFA biasa terletak pada domain fungsi transisi:

Artinya, transisi diperbolehkan menerima input simbol alfabet $\Sigma$ maupun simbol kosong $\epsilon$.

---

3. Konsep Kunci: $\epsilon$-Closure ($\text{ECLOSE}$)

Untuk setiap state $q \in Q$:

adalah himpunan semua state dalam $Q$ yang dapat dicapai dari state $q$ hanya dengan menelusuri transisi bertanda $\epsilon$ (termasuk rantai transisi $\epsilon \to \epsilon \to \dots$).

Sifat Mutlak:

1. Refleksif: Setiap state selalu termasuk ke dalam $\text{ECLOSE}$-nya sendiri melalui barisan $\epsilon$ kosong (panjang 0):

2. Transitif: Jika $p \in \text{ECLOSE}(q)$ dan $r \in \delta(p, \epsilon)$, maka $r \in \text{ECLOSE}(q)$.

Untuk sebuah himpunan state $S \subseteq Q$:

---

4. Extended Transition Function pada $\epsilon$-NFA

Pada DFA dan NFA biasa, membaca satu simbol $a$ cukup dengan $\delta(q, a)$. Namun pada $\epsilon$-NFA, mesin bisa melakukan transisi $\epsilon$ sebelum dan sesudah membaca simbol $a$!

Oleh karena itu, fungsi transisi satu simbol yang diperluas dirumuskan sebagai:

Tiga Tahap Eksekusi:

1. Ekspansi Awal: Cari seluruh state yang dapat dicapai dari $q$ via $\epsilon$ ($\text{ECLOSE}(q)$).

2. Konsumsi Input: Dari himpunan state tersebut, lakukan transisi dengan membaca simbol masukan $a$ ($\delta(\dots, a)$).

3. Ekspansi Akhir: Dari himpunan state hasil pembacaan, cari kembali seluruh state yang dapat dicapai via $\epsilon$ ($\text{ECLOSE}(\dots)$).

---

Studi Kasus & Perhitungan Evaluasi Transisi

Contoh Evaluasi Transisi State:

Diberikan konfigurasi automata di mana:

• Dari $q_0$, terdapat transisi $\epsilon$ ke $q_1$, dan dari $q_1$ terdapat transisi $\epsilon$ ke $q_3$.

• Maka: $\text{ECLOSE}(q_0) = \{q_0, q_1, q_3\}$.

• Nilai transisi langsung: $\delta(q_0, \epsilon) = \{q_1\}$.

• Nilai extended transition dengan $\epsilon$: $\hat{\delta}(q_0, \epsilon) = \text{ECLOSE}(q_0) = \{q_0, q_1, q_3\}$.

• Jika dari state $q_1$ ada transisi dengan simbol $0$ menuju $q_1$, dan dari $q_3$ ada transisi dengan simbol $0$ menuju $q_3$:

---

Algoritma Konversi $\epsilon$-NFA ke NFA Biasa (Tanpa $\epsilon$)

Untuk mengeliminasi seluruh transisi $\epsilon$ dan menghasilkan NFA standar $N' = (Q, \Sigma, \delta', q_0, F')$:

1. Himpunan state $Q$ dan alfabet $\Sigma$ tetap sama.

2. State awal tetap $q_0$.

3. Tentukan fungsi transisi baru $\delta'$ untuk setiap $q \in Q$ dan $a \in \Sigma$:

4. Tentukan himpunan state final baru $F'$:

(Jika dari state $q$ kita bisa mencapai salah satu state final lama hanya via $\epsilon$, maka $q$ otomatis dijadikan state final pada NFA baru).

---

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Jelaskan apa yang dimaksud dengan $\epsilon$-move dan apakah keberadaannya meningkatkan daya komputasi (computational power) dari Finite Automata?

Soal 1.2

Apa arti dari pernyataan $q \in \text{ECLOSE}(q)$?

---

Pembahasan/Jawaban

1.1 $\epsilon$-move adalah transisi yang terjadi tanpa mengkonsumsi/membaca simbol masukan dari pita input. Fitur ini tidak meningkatkan daya komputasi FA; bahasa yang dikenali tetaplah persis kelas Bahasa Reguler.

1.2 Pernyataan tersebut menyatakan sifat refleksif: setiap state selalu dapat mencapai dirinya sendiri melalui barisan transisi $\epsilon$ berpanjang 0 (tanpa melompat ke mana-mana).

---

Level 2 - Intermediate

Soal 2.1

Diberikan $\epsilon$-NFA dengan $Q = \{A, B, C\}$, transisi: $\delta(A, \epsilon) = \{B\}$, $\delta(B, \epsilon) = \{C\}$, $\delta(C, 0) = \{A\}$. Hitung: (a) $\text{ECLOSE}(A)$, (b) $\text{ECLOSE}(B)$, (c) $\text{ECLOSE}(C)$, dan (d) $\hat{\delta}(A, 0)$.

---

Pembahasan/Jawaban

• (a) Dari $A$ bisa ke $A$ (panjang 0), ke $B$ via $\epsilon$, dan ke $C$ via $B \xrightarrow{\epsilon} C$. Maka $\text{ECLOSE}(A) = \{A, B, C\}$.

• (b) Dari $B$ bisa ke $B$ dan ke $C$. Maka $\text{ECLOSE}(B) = \{B, C\}$.

• (c) Dari $C$ tidak ada transisi $\epsilon$ keluar. Maka $\text{ECLOSE}(C) = \{C\}$.

• (d) Menghitung $\hat{\delta}(A, 0)$:

  1. $\text{ECLOSE}(A) = \{A, B, C\}$
  2. $\delta(\{A, B, C\}, 0) = \delta(A, 0) \cup \delta(B, 0) \cup \delta(C, 0) = \emptyset \cup \emptyset \cup \{A\} = \{A\}$
  3. $\text{ECLOSE}(\{A\}) = \{A, B, C\}$

  Maka $\hat{\delta}(A, 0) = \{A, B, C\}$.

---

Level 3 - Advanced

Soal 3.1

Kapan state awal $q_0$ harus dimasukkan ke dalam himpunan state final $F'$ saat mengonversi $\epsilon$-NFA ke NFA biasa?

---

Pembahasan/Jawaban

State awal $q_0$ harus dimasukkan ke dalam $F'$ jika dan hanya jika $\text{ECLOSE}(q_0) \cap F \ne \emptyset$. Artinya, dari state awal $q_0$ terdapat jalur transisi $\epsilon$ murni yang mampu mencapai minimal satu state final tanpa membaca satu pun simbol input. Hal ini menandakan bahwa string kosong $\epsilon$ termasuk anggota bahasa yang diterima ($\epsilon \in L(N)$).

---

Exam Cheat Sheet

• Definisi Fungsi Transisi: $\delta : Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q$.

• Rumus Evaluasi Transisi Utama:

• Kondisi Penerimaan: $\hat{\delta}(q_0, w) \cap F \ne \emptyset$.

• Aturan State Final Baru: $F' = \{q \mid \text{ECLOSE}(q) \cap F \ne \emptyset\}$.

• Manfaat Utama: Modularitas perancangan (penggabungan union dua automata secara praktis).

---

Referensi & Bahan Bacaan

1. Hopcroft, John E., Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory (Section 2.5: Finite Automata With Epsilon-Transitions).

2. Michael Sipser. Introduction to the Theory of Computation (Equivalence of NFA and Epsilon-NFA).

Catatan Penutup

Setelah menguasai automata pengenal bahasa murni (Accept/Reject), pada bab berikutnya, Chapter 6: Moore dan Mealy, kita akan mempelajari automata yang menghasilkan deretan keluaran (Finite State Transducers).