Modul 3
Pushdown Automata (PDA) & Context-Free Grammar (CFG)
PDA adalah FSA yang dilengkapi stack (tumpukan memori). CFG adalah himpunan aturan produksi untuk men-generate string. Keduanya setara dalam mengenali Context-Free Language.
Ringkasan Teori:
FSA/DFA/NFA tidak bisa mengenali bahasa seperti
FSA/DFA/NFA tidak bisa mengenali bahasa seperti
L = {0n1n} karena butuh "mengingat" jumlah simbol.
PDA menambahkan stack: setiap kali baca '0', push ke stack; setiap baca '1', pop dari stack;
diterima jika stack kosong di akhir. CFG mendefinisikan bahasa yang sama melalui aturan produksi rekursif,
misalnya S → 0S1 | ε.
Definisi PDA
Field
push berupa list, elemen TERAKHIR = top of stack setelah push.
Gunakan "eps" untuk transisi tanpa membaca input.
Jejak Konfigurasi PDA (state, input tersisa, isi stack)
| # | State | Baca | Pop | Push | Stack Setelahnya (top di kanan) | Sisa Input |
|---|
Definisi CFG
Gunakan
"eps" pada produksi untuk merepresentasikan string kosong (ε).Langkah Derivasi (Leftmost Derivation)