Chapter 2: Finite State Machine (FSM), Operasi String, dan Bahasa Formal - Academics

Konsep & Pembahasan Terperinci

1. Kegunaan FSM dan Perumusan Masalah Komputasi

A. Empat Bidang Kegunaan FSM menurut Materi

Software untuk desain dan verifikasi rangkaian digital: Memodelkan gerbang logika sekuensial dan register.
Lexical analyzer pada compiler: Mengenali token seperti kata kunci (if, while), identifier, dan literal angka.
Pencarian pada teks yang besar: Digunakan pada search engine web, utility grep, dan pencocokan pola regex.
Desain, verifikasi, dan implementasi sistem software interaktif: Protokol jaringan (TCP/IP), transaksi electronic commerce, dan sistem reaktif.

B. Perumusan Masalah (Problem to Resolve)

Dalam teori bahasa dan automata, suatu masalah komputasi didefinisikan sebagai masalah keanggotaan bahasa (membership decision problem):

Diberikan sebuah bahasa $L \subseteq \Sigma^*$ .
Diberikan sebuah input berupa string sembarang $x \in \Sigma^*$ .
Tantangan: Menentukan secara pasti apakah $x \in L$ atau $x \notin L$ .
Mesin automata bertugas menyelesaikan masalah tersebut dengan mengeluarkan keputusan:
- Accept (Terima) jika $x \in L$ .
- Reject (Tolak) jika $x \notin L$ .

2. Alfabet, String, String Kosong, dan Panjang String

Alfabet ( $\Sigma$ ): Himpunan berhingga simbol.
- Contoh biner: $\Sigma = \{0, 1\}$
- Contoh alfabet huruf kecil: $\Sigma = \{a, b, c, \dots, z\}$
- Contoh ASCII: $\Sigma = \text{semua karakter ASCII}$
String ( $w$ ): Barisan berhingga $w = w_1 w_2 \dots w_n$ di mana setiap $w_i \in \Sigma$ .
- Contoh: $101$, $\text{string}$ , $\text{Rp 1.000.000}$ .
String Kosong ( $\epsilon$ ): String dengan 0 simbol.
- Sifat identitas: $\epsilon w = w \epsilon = w$ .
- Sebagai contoh konkret: $\epsilon \cdot abba = abba \cdot \epsilon = abba$ .
Panjang String ( $|w|$ ): Jumlah karakter dalam string.
- $|\epsilon| = 0$
- $|1001| = 4$
- $|\text{string}| = 6$

3. Perkalian Cartesian, Star Closure, dan Positive Closure

A. Perkalian Cartesian ( $\Sigma^k$ )

$\Sigma^k$ merepresentasikan himpunan semua string dengan panjang tepat $k$ yang dibentuk dari simbol-simbol $\Sigma$ .

Sebagai contoh: Jika $A = \{a, b\}$ dan $B = \{0, 1, 2\}$ , maka:

A \times B = \{(a,0), (a,1), (a,2), (b,0), (b,1), (b,2)\}

|A \times B| = |A| \times |B| = 2 \times 3 = 6

Untuk alfabet biner $\Sigma = \{0, 1\}$ :
- $\Sigma^0 = \{\epsilon\}$
- $\Sigma^1 = \{0, 1\}$
- $\Sigma^2 = \{00, 01, 10, 11\}$
- $\Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}$

B. Star Closure Kleene ( $\Sigma^*$ )

Himpunan seluruh string berhingga dari $\Sigma$ , termasuk string kosong:

\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, \dots\}

Catatan Konseptual: Meskipun setiap elemen dalam $\Sigma^*$ memiliki panjang berhingga, himpunan $\Sigma^*$ itu sendiri berukuran tak terhingga (infinite set).

C. Positive Closure ( $\Sigma^+$ )

Himpunan seluruh string berhingga dari $\Sigma$ tanpa string kosong:

\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \dots = \Sigma^* - \{\epsilon\} = \{0, 1, 00, 01, 10, 11, \dots\}

Hubungan mendasar: $\Sigma^* = \Sigma^+ \cup \{\epsilon\}$ .

4. Definisi Bahasa dan Operasi Himpunan Bahasa

Suatu bahasa $L$ atas alfabet $\Sigma$ adalah sembarang subset dari $\Sigma^*$ ( $L \subseteq \Sigma^*$ ). Sebagai contoh konkret:

Jika $\Sigma = \{a, b, \dots, z\}$ , maka $L = \text{semua kata dalam bahasa Indonesia}$ .
Jika $\Sigma = \{0, 1\}$ , maka $L = \{\epsilon, 01, 0011, 000111, \dots\} = \{0^n 1^n \mid n \ge 0\}$ .
Jika $\Sigma = \text{ASCII}$ , maka $L = \text{semua program C++ yang dapat di-compile}$ .

5. Tiga Pola Bahasa Dasar (Penting untuk Ujian)

Terdapat tiga pola ekspresi dasar yang penting untuk dipahami batasannya:

Pola Bahasa	Definisi & Karakteristik	Contoh Anggota Bahasa
*$(a+b)^$**	Bahasa yang terbentuk dari semua kata dari huruf $a$ atau $b$ atau keduanya secara bebas	$\epsilon, a, b, ab, ba, aa, bb, aba, bab, bbaa, abba, \dots$
*$a^b^$*	Bahasa yang terbentuk dari $a$ dan $b$ bebas, tetapi tidak mungkin ada huruf $a$ setelah huruf $b$	$\epsilon, a, b, aa, bb, ab, aab, aabb, abbb, \dots$ (string $ba$ atau $abba$ bukan anggota!)
*$(ab)^$**	Bahasa yang terbentuk dari pengulangan blok pasangan $ab$	$\epsilon, ab, abab, ababab, \dots$

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan 4 kegunaan utama FSM dalam rekayasa perangkat lunak dan komputasi.

Soal 1.2

Jika $\Sigma = \{0, 1\}$ , tentukan anggota dari $\Sigma^0$ , $\Sigma^1$ , dan $\Sigma^2$ .

Soal 1.3

Jelaskan perbedaan mendasar antara $\Sigma^*$ dan $\Sigma^+$ .

Pembahasan/Jawaban

1.1 Empat penerapan penting automata:

Software desain dan verifikasi rangkaian digital
Lexical analyzer pada compiler
Pencarian teks besar (search engine, grep)
Desain, verifikasi, dan implementasi sistem software interaktif (protokol jaringan, e-commerce, sistem reaktif)

1.2 $\Sigma^0 = \{\epsilon\}$ , $\Sigma^1 = \{0, 1\}$ , $\Sigma^2 = \{00, 01, 10, 11\}$ .

1.3 $\Sigma^*$ memuat string kosong $\epsilon$ ( $\Sigma^* = \bigcup_{i=0}^\infty \Sigma^i$ ), sedangkan $\Sigma^+$ tidak memuat string kosong ( $\Sigma^+ = \Sigma^* - \{\epsilon\}$ ).

Level 2 - Intermediate

Soal 2.1

Diberikan bahasa $L = \{a^n b^n \mid n \ge 0\}$ . Tentukan $L^R$ (reversal) dan jelaskan mengapa string $abba$ tidak termasuk ke dalam $L$ .

Soal 2.2

Diberikan $L_1 = \{a, ab, aaaa\}$ dan $L_2 = \{bb, ab\}$ . Hitung: (a) $L_1 \cup L_2$ , (b) $L_1 \cap L_2$ , dan (c) $L_1 - L_2$ .

Pembahasan/Jawaban

2.1 $L^R = \{b^n a^n \mid n \ge 0\}$ . String $abba$ memiliki dua huruf $a$ dan dua huruf $b$ , namun urutannya diawali $a$ , diakhiri $a$ , bukan seluruh $a$ mendahului seluruh $b$ . Pada $L$ , untuk panjang 4 dengan $n=2$ , string yang sah hanyalah $a^2 b^2 = aabb$ .

2.2

(a) $L_1 \cup L_2 = \{a, ab, bb, aaaa\}$
(b) $L_1 \cap L_2 = \{ab\}$
(c) $L_1 - L_2 = \{a, aaaa\}$

Level 3 - Advanced

Soal 3.1

Analisis mengapa string $bbaa$ diterima oleh pola $(a+b)^*$ , tetapi ditolak oleh pola $a^*b^*$ dan $(ab)^*$ .

Pembahasan/Jawaban

Pada pola $(a+b)^*$ , seluruh permutasi kombinasi simbol $a$ dan $b$ dengan panjang berapapun diperbolehkan, sehingga $bbaa \in (a+b)^*$ .

Pada pola $a^*b^*$ , terdapat aturan mutlak bahwa tidak boleh ada simbol $a$ yang muncul setelah simbol $b$ . Karena pada string $bbaa$ terdapat simbol $a$ setelah simbol $b$ , maka $bbaa \notin a^*b^*$ .

Pada pola $(ab)^*$ , string harus tersusun atas kelipatan pasangan terurut $ab$ . Karena $bbaa$ tidak tersusun atas blok $ab$ , maka $bbaa \notin (ab)^*$ .

Exam Cheat Sheet

Kardinalitas: $|A \times B| = |A| \times |B|$ .
Panjang String Kosong: $|\epsilon| = 0$ , identitas: $\epsilon w = w \epsilon = w$ .
Hubungan Kleene Star & Positive Closure: $\Sigma^* = \Sigma^+ \cup \{\epsilon\}$ dan $\Sigma^+ = \Sigma^* - \{\epsilon\}$ .
Komplemen Bahasa: $\overline{L} = \Sigma^* - L$ .
Sifat Reversal Konkatenasi: $(xy)^R = y^R x^R$ .
3 Pola Wajib Paham:
- $(a+b)^*$ : Sembarang kombinasi $a$ dan $b$ .
- $a^*b^*$ : $a$ dulu baru $b$ , pantang ada $a$ setelah $b$ .
- $(ab)^*$ : Pengulangan pola pasangan $ab$ .

Referensi & Bahan Bacaan

Catatan Penutup

Bab 2 telah memformalkan konsep dasar simbol, alfabet, operasi string, dan pola bahasa. Pada bab berikutnya, Chapter 3: Finite Automata (FA), kita akan mempelajari mesin komputasi pertama yang mengimplementasikan proses penerimaan bahasa-bahasa ini.