Chapter 3: Finite Automata (FA) dan Fungsi Transisi Induktif - Academics

Konsep & Pembahasan Terperinci

1. Hakikat FA: Mesin Komputasi Tanpa Memori

Finite Automaton (FA) adalah model komputasi matematis yang paling mendasar:

Tanpa Penyimpanan Sementara: FA tidak memiliki pita memori tambahan atau stack. FA hanya "mengingat" kondisi masa lalu melalui state aktif saat ini.
Kelas Bahasa: FA melingkupi kelas bahasa reguler (Regular Language).
Mekanisme Pemindaian: FA membaca pita masukan dari kiri ke kanan secara searah (tidak pernah mundur atau membaca ulang simbol yang telah dilewati).

2. Definisi Formal 5-Tuple Finite Automaton

Suatu Finite Automaton didefinisikan secara matematis oleh 5 komponen:

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

Di mana:

$Q$ : Himpunan berhingga semua keadaan (finite set of states).
$\Sigma$ : Alfabet masukan (finite input alphabet).
$q_0$ : Keadaan awal (start/initial state), di mana $q_0 \in Q$ .
$F$ : Himpunan keadaan akhir/penerima (final/accepting states), di mana $F \subseteq Q$ .
$\delta$ : Fungsi transisi (transition function), memetakan pasangan state dan simbol masukan ke tepat satu state berikutnya:

\delta : Q \times \Sigma \longrightarrow Q

3. Extended Transition Function ( $\hat{\delta}$ )

Fungsi transisi standar $\delta(q, a)$ hanya mendefinisikan transisi untuk sebuah simbol tunggal $a \in \Sigma$ . Untuk melacak perpindahan state ketika membaca seluruh kata/string $w \in \Sigma^*$ , materi merumuskan Extended Transition Function ( $\hat{\delta}$ atau $\tilde{\delta}$ ):

\hat{\delta} : Q \times \Sigma^* \longrightarrow Q

Formulasi Induktif Formal:

Untuk setiap $q \in Q$ , $a \in \Sigma$ , dan $x \in \Sigma^*$ :

Basis:

\hat{\delta}(q, \epsilon) = q

(Membaca string kosong tidak mengubah state)

Induksi:

\hat{\delta}(q, xa) = \delta(\hat{\delta}(q, x), a)

(Membaca string $xa$ setara dengan membaca seluruh prefiks $x$ terlebih dahulu hingga mencapai suatu state, lalu melakukan satu transisi $\delta$ dengan simbol terakhir $a$ )

Studi Kasus & Tracing: Mesin Penguji Substring '01'

Spesifikasi Mesin

Alfabet: $\Sigma = \{0, 1\}$
Bahasa: $L = \{w \in \{0, 1\}^* \mid w \text{ memuat substring } 01\} = \{x01y \mid x, y \in \{0, 1\}^*\}$
Himpunan State: $Q = \{q_0, q_1, q_2\}$
State Awal: $q_0$
State Akhir: $F = \{q_2\}$

Semantik Penjelasan State:

$q_0$ : Kondisi awal, sedang menunggu kemunculan simbol 0 yang pertama.
$q_1$ : Telah menerima minimal satu simbol 0, sedang menunggu kemunculan simbol 1 berikutnya.
$q_2$ : Telah berhasil menemukan substring 01, berada pada kondisi penerimaan (accepting) dan menunggu akhir dari string input.

Tabel Transisi Mesin

State ( $Q$ )	Input $0$	Input $1$
$\to q_0$	$q_1$	$q_0$
$q_1$	$q_1$	$q_2$
$*q_2$	$q_2$	$q_2$

Pelacakan (Tracing) Langkah demi Langkah

Kasus 1: String Masukan $w = 11010$ (Harus Diterima)

Pelacakan menggunakan formulasi induktif $\hat{\delta}$ :

$\hat{\delta}(q_0, \epsilon) = q_0$
$\hat{\delta}(q_0, 1) = \delta(q_0, 1) = q_0$
$\hat{\delta}(q_0, 11) = \delta(\hat{\delta}(q_0, 1), 1) = \delta(q_0, 1) = q_0$
$\hat{\delta}(q_0, 110) = \delta(\hat{\delta}(q_0, 11), 0) = \delta(q_0, 0) = q_1$
$\hat{\delta}(q_0, 1101) = \delta(\hat{\delta}(q_0, 110), 1) = \delta(q_1, 1) = q_2$
$\hat{\delta}(q_0, 11010) = \delta(\hat{\delta}(q_0, 1101), 0) = \delta(q_2, 0) = q_2$

Karena state akhir $q_2 \in F$ , maka string $11010$ Diterima (Accepted).

Kasus 2: String Masukan $w = 111000$ (Harus Ditolak)

$\hat{\delta}(q_0, 1) = q_0$
$\hat{\delta}(q_0, 11) = q_0$
$\hat{\delta}(q_0, 111) = q_0$
$\hat{\delta}(q_0, 1110) = q_1$
$\hat{\delta}(q_0, 11100) = q_1$
$\hat{\delta}(q_0, 111000) = q_1$

Karena state akhir $q_1 \notin F$ , maka string $111000$ Ditolak (Rejected).

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan 5 komponen dalam tuple formal Finite Automaton $A = (Q, \Sigma, \delta, q_0, F)$ .

Soal 1.2

Tuliskan rumus basis dan langkah induksi dari Extended Transition Function ( $\hat{\delta}$ ).

Pembahasan/Jawaban

1.1 Komponen 5-tuple FA:

$Q$ : himpunan berhingga state
$\Sigma$ : alfabet input berhingga
$\delta$ : fungsi transisi $Q \times \Sigma \to Q$
$q_0$ : state awal ( $q_0 \in Q$ )
$F$ : himpunan state final ( $F \subseteq Q$ )

1.2 Basis: $\hat{\delta}(q, \epsilon) = q$ . Induksi: $\hat{\delta}(q, xa) = \delta(\hat{\delta}(q, x), a)$ untuk $x \in \Sigma^*$ dan $a \in \Sigma$ .

Level 2 - Intermediate

Soal 2.1

Lakukan tracing induktif untuk string $w = 000111$ pada mesin penguji substring 01 di atas, dan tentukan apakah string tersebut diterima atau ditolak.

Pembahasan/Jawaban

Baca 0: $q_0 \to q_1$
Baca 0: $q_1 \to q_1$
Baca 0: $q_1 \to q_1$
Baca 1: $q_1 \to q_2$ (substring 01 ditemukan!)
Baca 1: $q_2 \to q_2$
Baca 1: $q_2 \to q_2$

Akhir string berada di state $q_2 \in F$ . String diterima (Accepted).

Level 3 - Advanced

Soal 3.1

Mengapa FA tidak mampu mengenali bahasa $L = \{0^n 1^n \mid n \ge 1\}$ di mana jumlah 0 harus persis sama dengan jumlah 1? Jelaskan kaitannya dengan sifat fundamental FA.

Pembahasan/Jawaban

Secara fundamental, FA merupakan mesin komputasi yang tidak mempunyai penyimpanan/memori sementara. Karena nilai $n$ tidak terbatas ( $n \ge 1$ ), mesin membutuhkan memori penghitung tak terbatas untuk mencatat berapa banyak simbol 0 yang sudah lewat sebelum mencocokkannya dengan simbol 1. Karena himpunan state $Q$ pada FA berhingga (finite), FA tidak sanggup menyimpan informasi penghitungan tak hingga tersebut dan pasti gagal membedakan string saat $n > |Q|$ .

Exam Cheat Sheet

5-Tuple FA: $A = (Q, \Sigma, \delta, q_0, F)$ .
Pemetaan Fungsi Transisi: $\delta : Q \times \Sigma \to Q$ .
Extended Transition Function: $\hat{\delta}(q, \epsilon) = q$ dan $\hat{\delta}(q, xa) = \delta(\hat{\delta}(q, x), a)$ .
Syarat String Diterima: $\hat{\delta}(q_0, w) \in F$ .
Karakteristik Utama: Membaca string satu arah (kiri ke kanan), tidak punya memori sementara, mengenali bahasa reguler.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 3 memformalkan cara kerja Finite Automata yang deterministik. Pada bab selanjutnya, Chapter 4: DFA dan NFA, kita akan membandingkan FA deterministik dengan model non-deterministik (NFA) yang memiliki kemampuan membuat percabangan eksekusi.