Matdis — Bab 12
Automata & Bahasa Formal
Mesin abstrak yang mendefinisikan batas komputasi — dari ekspresi reguler dan compiler hingga model checking dan verifikasi formal.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 12. — Sipser, Introduction to the Theory of Computation, 3rd ed., Ch. 1–5. — Hopcroft, Motwani & Ullman, Introduction to Automata Theory, 3rd ed.
Mengapa Automata?
Sebelum komputer fisik ada, Alan Turing (1936) dan lainnya membangun model matematis mesin yang menghitung. Hasilnya mengejutkan: ada hierarki kekuatan komputasi (DFA < PDA < TM), dan ada masalah yang secara provable tidak dapat diselesaikan oleh mesin manapun (halting problem).
Aplikasi modern: regex (text processing, lexer compiler), parser (semua bahasa pemrograman), TLS state machine, model checking (ProVerif, Tamarin untuk verifikasi protokol crypto), dan side-channel analysis (memodelkan power traces sebagai DFA tersembunyi).
1. Alfabet, String, dan Bahasa
Konsep Dasar
Alfabet (Σ): himpunan berhingga simbol. Contoh: Σ = {0,1}, Σ = {a,b,c,...,z}.
String (w): barisan hingga simbol dari Σ. Panjang |w|. String kosong: ε, |ε|=0.
Σ*: himpunan semua string atas Σ (termasuk ε). Tak hingga tapi countable.
Bahasa (L): himpunan string atas Σ. L ⊆ Σ*. Bisa hingga atau tak hingga.
Operasi bahasa: union (L₁∪L₂), concatenation (L₁L₂), Kleene star (L*).
Komplemen: L̄ = Σ* \ L (semua string yang tidak di L).
Analogi: Lampu Lalu Lintas
DFA adalah seperti lampu lalu lintas: memiliki state terbatas (merah/kuning/hijau), transisi berdasarkan input (timer/sensor mobil), dan setiap input di state tertentu memberikan state berikutnya yang unik dan deterministik. Tidak perlu ingat "history" — hanya state saat ini yang relevan.
2. DFA — Deterministic Finite Automaton
Definisi Formal
DFA adalah 5-tuple M = (Q, Σ, δ, q₀, F):
Q: himpunan berhingga state.
Σ: alfabet input.
δ: Q × Σ → Q: fungsi transisi deterministik — satu input, satu next state.
q₀ ∈ Q: start state.
F ⊆ Q: himpunan accepting (final) state (ditandai double circle).
String w diterima M jika δ*(q₀, w) ∈ F. Bahasa L(M) = {w : M menerima w}.
DFA 1: Menerima String dengan Jumlah '1' Genap
Simulator DFA 1: Jumlah '1' Genap
Langkah 1: baca '1' di q0 → q1
Langkah 2: baca '1' di q1 → q0
Langkah 3: baca '0' di q0 → q0
Langkah 4: baca '1' di q0 → q1
Berakhir di q1 ⟹ DITOLAK ✗
DFA 2: Menerima String Berakhiran "01"
State akhir: q2 ⟹ DITERIMA ✓ (berakhiran "01")
3. NFA — Non-deterministic Finite Automaton
Definisi (NFA)
Sama seperti DFA tetapi fungsi transisi δ: Q × (Σ ∪ {ε}) → P(Q) — satu input bisa ke banyak state, dan transisi ε (tanpa input) diizinkan.
Penerimaan: string w diterima jika ada jalur komputasi dari q₀ ke state accepting.
ε-closure(S): himpunan state yang dapat dicapai dari S via nol atau lebih ε-transisi.
Kegunaan: NFA lebih mudah dikonstruksi (terutama untuk union, concatenation, Kleene star), tapi ekuivalen dengan DFA.
Teorema Subset Construction (Rabin-Scott 1959)
Setiap NFA dengan n state dapat diekuivalenkan dengan DFA menggunakan paling banyak 2ⁿ state (subset state NFA).
Konstruksi: State DFA = subset state NFA. Mulai dari ε-closure({q₀}). Untuk subset S dan simbol a: δ_DFA(S,a) = ε-closure(⋃_{q∈S} δ_NFA(q,a)).
Konsekuensi penting: NFA dan DFA mengenali kelas bahasa yang sama persis: regular languages.
4. Regular Languages & Regular Expressions
Definisi (Regular Expression)
RE didefinisikan rekursif atas alfabet Σ:
- ∅ (bahasa kosong), ε (string kosong), dan a ∈ Σ adalah RE dasar.
- Jika R, S adalah RE, maka R | S (union), RS (concatenation), R* (Kleene star), (R) adalah RE.
- Tidak ada RE lain selain yang dibentuk dari aturan 1-2.
Teorema Kleene (1956): Bahasa L regular ⟺ L diterima DFA ⟺ L diterima NFA ⟺ L dapat dideskripsikan RE.
Tester Regular Expression (JavaScript engine)
"1100" ✓ MATCH dengan /^[01]*0$/
Coba pattern: [01]*0 (berakhiran 0), (01)+ (satu atau lebih "01"), [01]{3} (panjang 3).
5. Pumping Lemma
Pumping Lemma untuk Regular Languages
Jika L regular dengan pumping length p, maka setiap w ∈ L dengan |w| ≥ p dapat dipecah w = xyz dengan:
- |y| ≥ 1 (bagian tengah tidak kosong),
- |xy| ≤ p (y berada dalam p karakter pertama),
- xy^i z ∈ L untuk semua i ≥ 0 (memompa y ke atas atau bawah tetap di L).
Kontrapositif (untuk membuktikan L tidak regular): Tunjukkan tidak ada p yang bekerja — pilih w ∈ L yang "sesuai target", cek semua pemecahan xyz, dan tunjukkan ada i yang membuat xy^iz ∉ L.
6. Context-Free Grammar & Pushdown Automaton
CFG (Context-Free Grammar)
G = (V, T, P, S): V = variabel, T = terminal, P = produksi A→γ, S = start.
# aⁿbⁿ (tidak regular)
S → aSb | ε
# Ekspresi aritmetika
E → E+T | T
T → T*F | F
F → (E) | id | num
PDA (Pushdown Automaton)
PDA = DFA + stack (memori LIFO tak terbatas). Mengenali bahasa context-free.
Teorema: L diterima PDA ⟺ L dapat di-generate CFG.
Stack memungkinkan "mengingat" berapa a yang sudah dibaca untuk aⁿbⁿ. Parser kompiler (LALR, LR) menggunakan PDA.
7. Turing Machine & Computability
Definisi (Turing Machine)
TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) dengan tape tak terbatas dan read-write head yang bisa bergerak kiri atau kanan.
Church-Turing Thesis: Setiap fungsi "intuitif komputabel" dapat dihitung TM. Tidak terbukti formal, tapi diterima sebagai aksioma CS.
Decidable: L decidable jika ada TM yang selalu berhenti dan menerima/menolak dengan benar.
Recognizable: L recognizable (RE) jika ada TM yang menerima w ∈ L (tapi mungkin loop pada w ∉ L).
Undecidable: masalah yang tidak ada TM yang menyelesaikannya. Contoh: Halting Problem.
Halting Problem (Turing 1936)
Tidak ada algoritma yang dapat menentukan, untuk setiap pasangan (M, w), apakah TM M berhenti pada input w.
Bukti (diagonalization): Misal ada H(⟨M,w⟩) yang memutuskan. Bangun D(⟨M⟩): jalankan H(⟨M,M⟩); jika accept, loop; jika reject, accept. Jalankan D(⟨D⟩) → kontradiksi.
Implikasi: Tidak ada tools otomatis yang bisa mengecek semua properties program secara general. Rice's Theorem: semua non-trivial semantic properties of programs are undecidable.
8. Hierarki Chomsky
Eksplorasi: Empat Tingkat Bahasa Formal
Type 3: Regular Language
Bentuk produksi: A → aB | a
Mesin yang mengenali: DFA / NFA
Contoh bahasa: a*b*, identifier, email regex
Paling terbatas — tidak bisa menghitung atau mengingat struktur bersarang.
Hierarki Inklusi Ketat
Regular ⊂ CFL ⊂ CSL ⊂ RE. Setiap inklusi adalah ketat (ada bahasa di kelas atas tapi tidak di bawah).
Koneksi ke Ilmu Komputer
Protocol State Machines: TLS 1.3 handshake adalah DFA formal: states {Start, Wait_ServerHello, Wait_Encrypted_Extensions, ..., Connected}. Verifikasi formal protokol kriptografi (miTLS, ProVerif) memodelkan handshake sebagai state machine dan membuktikan tidak ada jalur yang membocorkan kunci atau nonce.
Tamarin & ProVerif (Formal Verification): Tools untuk verifikasi otomatis protokol crypto. Memodelkan protokol Signal, TLS, WireGuard sebagai labeled transition systems. Membuktikan secrecy, authentication, dan forward secrecy secara formal. Kunci untuk mendeteksi flaws seperti Logjam, FREAK, KRACK sebelum deployment.
Decidability of Crypto Properties: Beberapa properties keamanan protokol (apakah dengan unbounded sessions aman) adalah undecidable — reduksi ke Halting Problem. Itulah mengapa ProVerif menggunakan bounded session analysis dan symbolic abstraction (Dolev-Yao model).
Regex DoS (ReDoS): NFA dengan backtracking dapat dipaksa eksponensial pada input tertentu. Engine RE2 (Google) yang mengkompilasi ke DFA menghindari ini tapi tidak mendukung backreference. Pelajaran: algoritma berbasis DFA lebih aman dan deterministik untuk security-critical applications.
10. Contoh Soal & Pembahasan
Soal 1: Konstruksi DFA
Buatlah DFA untuk L = {w ∈ {0,1}* : w berakhiran "01"}.
Soal 2: Regular Expression
Tulis RE untuk L = {string biner dengan panjang kelipatan 3}.
Soal 3: Pumping Lemma
Buktikan L = {aⁿbⁿ : n ≥ 0} tidak regular.
Soal 4: NFA→DFA Subset Construction
NFA dengan 4 state. Berapa maksimum state DFA ekuivalen?
Soal 5: CFG Palindrom Biner
Tulis CFG untuk bahasa palindrom biner: L = {w ∈ {0,1}* : w = rev(w)}.
Soal 6: Halting Problem
Sketsa argumen: mengapa Halting Problem undecidable?
Soal 7: Klasifikasi Bahasa
Klasifikasikan: L = {aⁿbⁿcⁿ : n ≥ 1} dalam hierarki Chomsky.
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 12.
Mudah
1. Sebutkan 4 komponen DFA (Deterministic Finite Automaton).
2. Apakah bahasa L = {aⁿbⁿ | n ≥ 0} regular? Berikan alasan singkat.
3. Tuliskan regex untuk: string biner yang diakhiri "01".
4. Apa perbedaan DFA dan NFA? Apakah keduanya setara dalam kekuatan komputasi?
Sedang
1. Konstruksi DFA yang menerima semua string biner dengan jumlah "1" ganjil.
2. Gunakan pumping lemma untuk membuktikan L={0ⁿ1ⁿ | n≥1} tidak regular.
3. Apa itu Context-Free Grammar (CFG)? Berikan CFG untuk L={aⁿbⁿ | n≥0}.
4. Jelaskan hierarki Chomsky dan posisikan DFA, PDA, TM dalam hierarki tersebut.
Sulit
1. Konstruksi NFA untuk regex (ab)*(ba|a)+ lalu konversi ke DFA menggunakan subset construction. Tunjukkan tabel transisi.
2. Buktikan menggunakan Pumping Lemma bahwa L = {w ∈ {a,b,c}* | #a(w) = #b(w) = #c(w)} bukan context-free.
3. Jelaskan hubungan Halting Problem dengan undecidability. Mengapa implikasi ini relevan untuk verifikasi formal protokol kriptografi?
Kasus Terintegrasi (2+ Topik)
Token kriptografis sering divalidasi dengan regex. Konstruksi DFA untuk regex [0-9A-Fa-f]{64} (hex string 64 karakter, format SHA-256 output). Jelaskan state yang diperlukan.
Buktikan L={0ⁿ1ⁿ0ⁿ | n≥1} bukan CFL menggunakan Pumping Lemma CFL. Klasifikasikan L dalam hierarki Chomsky.
Buktikan bahwa E_TM = {⟨M⟩ | L(M) = ∅} tidak decidable menggunakan reduksi dari HALT. Jelaskan implikasinya untuk verifikasi keamanan otomatis.