Push Down Automata (PDA)

Pengertian Push Down Automata

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Syarat Push Down Automata

- Ruas kiri haruslah tepat satu simbol Variabel

Contoh :

B → CDeFg

D → BcDe

Cara Kerja Push Down Automata

Mekanisme kerja memory stack adalah menyimpan input pertama pada alamat paling bawah, input berikutnya di simpan pada alamat di atasnya, dan input terakhir di simpan 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 Tupel:
Q = himpunan stateΣ = himpunan simbol input
T = simbol stack
Δ = fungsi transisi
S = state awal
F = state akhir
Z = top of stack

Jenis - Jenis Transisi Push Down Automata :

1. Ä yang merima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol simbol. Penggantian isi stack dilakukan dengan opersi push dan pop.

2. å. 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.

Sumber :

https://en.wikipedia.org/wiki/Pushdown_automaton

http://muslim-kekinian.blogspot.com/2016/04/pushdown-automata.html