Dari grammar bebas konteks ke PDA
Ikuti stack saat mengenali string dengan jumlah a dan b yang sama.
dasar #PDA
Yang akan kamu pahami
Turunkan string dari grammar dan cocokkan ide rekursi dengan push dan pop.
Konsep inti
Grammar S → aSb | ε menghasilkan aⁿbⁿ. PDA bisa mendorong satu simbol stack per a, lalu mengeluarkan satu simbol per b setelah pindah fase. Stack menyimpan jumlah a yang belum punya pasangan. Setelah mulai membaca b, a berikutnya ditolak.
Coba langkahnya
Telusuri string aabb dengan simbol dasar Z.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| Input | a | a | b | b |
| Stack (bawah ke atas) | Z | A | A | · |
| Status | push | push | · | · |
Cek pemahaman
Latihan UTS & UAS
- UAS 2025 · No. 3Telusuri stack PDA dan jelaskan bahasa yang diterima.