Push Down Automata ( PDA )

Push Down Automata (PDA)

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

    Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, , q 0 , Z 0 , δ, A), dimana :

Q : himpunan hingga stata, Σ : alfabet input, : alfabet stack, q 0 ∈ Q : stata awal, Z 0 ∈ : simbol awal stack, A ⊆ Q : himpunan stata penerima,

fungsi transisi δ : Q  (Σ ∪ {ε})     → 2 Q    *  (himpunan bagian dari Q    *)

    Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ , δ(q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α.

    Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :

q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca, dan α ∈ * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.

    Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ , dan β ∈ *. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ *. Dapat kita tuliskan

bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).

Sebuah PDA dinyatakan dengan :

Q         = himpunan state

Σ          = himpunan simbol input

T          = simbol stack

S          = state awal

F          = state akhir

Z          = top of stack

PDA memiliki 2 jenis transisi, yaitu 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. Jenis transisi yang kedua adalah transisi ε. 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 : http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda/