Push Down Automata (PDA), contohnya dan perbedaan PDA dan Mesin Turing

1.      -  Pengertian PDA

Push Down Automata (PDA)  merupakan mesin otomata dari bahasa bebas konteks.  PDA di gambarkan sebagai tempat penyipanan yang tidak terbatas berupa stack/tumpukan.

-         Contoh PDA

1.      Tupple PDA:

Q = {q1, q2}

∑ = {a,b}

Γ= {A,B,Z}

S = q1

Z = Z

F = {q2}

Fungsi Transisi

Δ(q1, ɛ, Z)=  {(q2, Z)}

Δ(q1, a, Z) = {(q1, AZ)}

Δ(q1, b, Z) = {(q1, BZ)}

Δ(q1, a, A) = {(q1, AA)}

Δ(q1, b, A) = {(q1, ɛ)}

Δ(q1, a, B) = {(q1, ɛ)}

Δ(q1, b, B) = {(q1, BB)}