Chapter 8: Regular Expression (Ekspresi Reguler) dan Teorema Arden - Academics

Konsep & Pembahasan Terperinci

1. Komponen dan Presedensi Aljabar Reguler

Aljabar ekspresi reguler dibangun dari tiga komponen dasar:

Union ( $+$ ): Pilihan logis (OR). Contoh: $L(a + b) = \{a, b\}$ .
Concatenation ( $\cdot$ ): Penyambungan berurutan (AND THEN). Biasanya titik penyambung dihilangkan ( $ab \equiv a \cdot b$ ).
Kleene Star Closure ( $*$ ): Pengulangan nol kali atau lebih.

Urutan Evaluasi Operator (Hierarki Presedensi):

Prioritas 1 (Tertinggi): Operator Closure ( $*$ ).
Prioritas 2 (Menengah): Operator Penyambungan ( $\cdot$ ).
Prioritas 3 (Terendah): Operator Penggabungan ( $+$ ).

Contoh Hierarki Evaluasi: Ekspresi $P + Q \cdot R^*$ dievaluasi sebagai $P + (Q \cdot (R^*))$ , bukan $(P + Q) \cdot R^*$ .

4 Identitas Krusial Kleene Star & Positive Closure:

$R^+ = R \cdot R^* = R^* \cdot R$
$R^* = \epsilon + R^+$
$L(\epsilon^*) = \{\epsilon\}$
$L(\emptyset^*) = \{\epsilon\}$ (Perhatikan: Pengulangan himpunan kosong nol kali menghasilkan string kosong $\epsilon$ !)

2. Algoritma Thompson: Konversi RE ke $\epsilon$ -NFA

Algoritma Thompson menyediakan blok pembangun (building blocks) modular:

Untuk $\epsilon$ : State awal {\text{in}} \xrightarrow{\epsilon} q_{\text{out}}$ (state final).
**Untuk simbol \in \Sigma $**: State awal {\text{in}} \xrightarrow{a} q_{\text{out}}$ (state final).
Untuk Union ( + R_2$): State awal baru bercabang $\epsilon$ ke start $ dan start $; final $ dan final $ bercabang $\epsilon$ ke state final baru.
Untuk Concatenation ( \cdot R_2$): Hubungkan state final $ ke state awal $ dengan transisi $\epsilon$.
Untuk Closure (^*$): Tambahkan loop $\epsilon$ dari final $ kembali ke awal $, dan buat jalur pintas (bypass) $\epsilon$ dari state awal baru langsung ke state final baru untuk mengakomodasi string kosong $\epsilon$.

Studi Kasus Thompson: = a^* + b \cdot c$

Ekspresi = a^* + b \cdot c$ tersusun atas dua sub-ekspresi yang digabung dengan union:

Cabang atas: ^*$ (Closure atas $).
Cabang bawah: \cdot c$ (Penyambungan $ lalu $).

1. Graf Thompson Lengkap:

State awal bercabang $\epsilon$ ke cabang atas ( $a^*$ ) dan cabang bawah ( $b \cdot c$ ).
Pada cabang atas: State awal $a$ memiliki bypass $\epsilon$ ke akhir dan loop balik $\epsilon$ setelah membaca $a$ .
Pada cabang bawah: Simbol $b$ dihubungkan via $\epsilon$ ke simbol $c$ .
Kedua cabang bermuara via transisi $\epsilon$ ke satu state final bersama.

2. Graf Transisi yang Disederhanakan:

Transisi $\epsilon$ internal yang berlebihan disederhanakan:

Cabang atas: Loop $a$ dan bypass $\epsilon$ dipadatkan.
Cabang bawah: Busur berurutan $b$ langsung menuju transisi $c$ .
Hasil automata mempertahankan ketepatan bahasa dengan jumlah state yang jauh lebih ringkas.

Teorema Arden: Mengubah DFA Menjadi Ekspresi Reguler

Teorema Arden digunakan untuk memecahkan sistem persamaan linear pada graf transisi:

Teorema Arden:

Jika $P$ dan $Q$ adalah dua ekspresi reguler di mana $\epsilon \notin P$ , maka persamaan:

R = Q + RP

memiliki solusi unik:

R = QP^*

Langkah Penerapan:

Nyatakan setiap state $q_i$ sebagai persamaan aljabar dari seluruh panah transisi yang masuk ke $q_i$ :

q_i = \sum q_j \cdot a_{ji} + (\epsilon \text{ jika } q_i \text{ adalah state awal } q_0)

Gunakan substitusi aljabar dan Teorema Arden ( $R = Q + RP \implies R = QP^*$ ) hingga diperoleh nilai ekspresi reguler murni untuk setiap state final.
Ekspresi reguler keseluruhan adalah gabungan ( $+$ ) dari solusi seluruh state final.

Latihan Soal & Pembahasan

Level 1 - Basic

Soal 1.1

Sebutkan urutan presedensi dari ketiga operator dalam ekspresi reguler ( $*$ , $+$ , $\cdot$ ).

Soal 1.2

Buktikan bahwa $L(\emptyset^*) = \{\epsilon\}$ .

Pembahasan/Jawaban

1.1 Presedensi tertinggi adalah Closure ( $*$ ), diikuti Concatenation ( $\cdot$ ), dan terendah adalah Union ( $+$ ).

1.2 Berdasarkan definisi perpangkatan bahasa, $L^0 = \{\epsilon\}$ untuk sembarang bahasa $L$ , termasuk $L = \emptyset$ . Karena $\emptyset^* = \emptyset^0 \cup \emptyset^1 \cup \dots = \{\epsilon\} \cup \emptyset = \{\epsilon\}$ .

Level 2 - Intermediate

Soal 2.1

Diberikan $R = \epsilon + 1$ dan $S = \epsilon + 0 + 1$ . Hitung bahasa hasil konkatenasi $T = R \cdot S$ secara eksplisit.

Pembahasan/Jawaban

$L(R) = \{\epsilon, 1\}$ dan $L(S) = \{\epsilon, 0, 1\}$ .

L(T) = L(R) \cdot L(S) = \{\epsilon \cdot \epsilon, \epsilon \cdot 0, \epsilon \cdot 1, 1 \cdot \epsilon, 1 \cdot 0, 1 \cdot 1\} = \{\epsilon, 0, 1, 1, 10, 11\} = \{\epsilon, 0, 1, 10, 11\}

(Catatan: perhitungan aljabar lengkapnya menghasilkan $\{\epsilon, 0, 1, 10, 11\}$ ).

Level 3 - Advanced

Soal 3.1

Gunakan Teorema Arden untuk mencari ekspresi reguler dari state $q_1$ jika diketahui persamaan:

q_1 = q_1 0 + 1

di mana $1$ adalah input dari state sebelumnya dan $0$ adalah self-loop pada $q_1$ .

Pembahasan/Jawaban

Bentuk persamaan: $q_1 = 1 + q_1 \cdot 0$ .

Pencocokan pola dengan Teorema Arden $R = Q + RP$ :

$R = q_1$
$Q = 1$
$P = 0$ (karena $\epsilon \notin \{0\}$ , syarat terpenuhi)

Solusi unik menurut Teorema Arden adalah:

R = QP^* \implies q_1 = 1 \cdot 0^* = 10^*

Exam Cheat Sheet

Presedensi Operator: $* > \cdot > +$ .
Identitas Kunci:
- $R^+ = R R^* = R^* R$
- $R^* = \epsilon + R^+$
- $\emptyset^* = \{\epsilon\}$
Formula Teorema Arden:

R = Q + RP \implies R = QP^* \quad (\text{syarat: } \epsilon \notin P)

Konstruksi Thompson: Memetakan setiap operator RE ke modul $\epsilon$ -NFA terstandarisasi.

Referensi & Bahan Bacaan

Catatan Penutup

Bab 8 menutup pembahasan kelas Bahasa Reguler dari sudut pandang aljabar. Pada bab berikutnya, Chapter 9: Context Free Grammar (CFG), kita melangkah keluar dari batas bahasa reguler untuk mempelajari tata bahasa rekursif yang melandasi perancangan kompilator modern.