Pushdown Automata
Pushdown Automata (PDA) adalah finite automata dengan memori ekstra yang disebut sebagai “stack”, yang membantu PDA untuk mengenali Context Free Languages.
Mekanisme kerja memori stack adalah menyimpan input pertama pada alamat paling bawah, input berikutnya disimpan pada alamat di atasnya, dan input terakhir disimpan pada alamat paling atas. Perintah operasi yang digunakan untuk menyimpan input pada stack adalah “push”. Sedangkan perintah operasi untuk mengeluarkan input yang telah tersimpan adalah “pop”.
Sebuah PDA dinyatakan dengan 7-tuple (Q, Σ, T, δ, S, F, Z) di mana:
Q = Himpunan State
Σ = Himpunan simbol input
T = Simbol stack
δ = Fungsi transisi
S = State awal
F = State akhir
Z = Top of stack
PDA memiliki 2 jenis transisi, yaitu:
– Ä yang menerima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol-simbol. Penggantian isi stack dilakukan dengan operasi push and pop.
– å. Transisi å tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.
Contoh operasi:
Mekanisme kerja memori stack adalah menyimpan input pertama pada alamat paling bawah, input berikutnya disimpan pada alamat di atasnya, dan input terakhir disimpan pada alamat paling atas. Perintah operasi yang digunakan untuk menyimpan input pada stack adalah “push”. Sedangkan perintah operasi untuk mengeluarkan input yang telah tersimpan adalah “pop”.
Sebuah PDA dinyatakan dengan 7-tuple (Q, Σ, T, δ, S, F, Z) di mana:
Q = Himpunan State
Σ = Himpunan simbol input
T = Simbol stack
δ = Fungsi transisi
S = State awal
F = State akhir
Z = Top of stack
PDA memiliki 2 jenis transisi, yaitu:
– Ä yang menerima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol-simbol. Penggantian isi stack dilakukan dengan operasi push and pop.
– å. Transisi å tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.
Contoh operasi: