Tugas Teknik Kompilasi - 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.

Deterministik Push Down Automata (PDA)

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

Stack ialah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack). Prinsip pada stack adalah LIFO.  Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen ke dalam stack dengan operasi push.

Contoh stack :

perasi pop :

Jika dilakukan operasi push B, maka kondisi stack akan menjadi :

Definisi : PDA adalah pasangan 7 tuple.

M = (Q, S, q, F, d, G, Z), dimana :

Q : himpunan hingga state,

S : alfabet input,

G : alfabet/simbol stack,

q: state awal, qÎ Q

Z : simbol awal stack,  ZÎ G

F : himpunan state penerima, F Í Q

d : fungsi transisi , d : Q ´ (S È {e}) ´ G ® 2 (himpunan bagian dari Q ´ G*)

d(q, a, Z) = (q, AZ).     Push/insert

d(q, a, A) = (q1, e).               Pop /delete

Untuk state q Î Q, simbol input a Î S, dan simbol stack XÎ G, d(q, a, X) = (p, a) berarti : PDA bertransisi ke state p dan mengganti X pada stack dengan string a.

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

q Î Q : state pada saat tersebut, x Î S* : bagian string input yang belum dibaca, dan a Î G* : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.

Misalkan (p, ay, Xb) adalah sebuah konfigurasi, dimana : a Î S, y Î S*, X Î G, dan b Î G*. Misalkan pula d(p, a, X) = (q, g) untuk q Î Q dan g Î G*. Dapat kita tuliskan bahwa : (p, ay, Xb) Þ (q, y, gb).

[M. Aldi Pratama] PDA dan CFL (Context Free Languages)

Dalam teori bahasa formal , bahasa bebas konteks ( CFL ) adalah bahasa yang dihasilkan oleh beberapa bebas konteks tata bahasa ( CFG ) . tata bahasa CF yang berbeda dapat menghasilkan bahasa CF yang sama . Hal ini penting untuk membedakan sifat dari bahasa ( sifat intrinsik ) dari sifat dari tata bahasa tertentu ( sifat ekstrinsik ) .

Himpunan semua bahasa bebas konteks identik dengan set bahasa diterima oleh pushdown automata , yang membuat bahasa ini setuju untuk parsing . Memang , diberi CFG , ada cara langsung untuk menghasilkan robot pushdown untuk tata bahasa ( dan bahasa yang sesuai ) , meskipun pergi ke arah lain ( menghasilkan tata bahasa diberikan robot ) tidak sebagai langsung .

bahasa bebas konteks memiliki banyak aplikasi dalam bahasa pemrograman ; misalnya , bahasa semua kurung benar cocok dihasilkan oleh tata bahasa { \ displaystyle S \ ke SS ~ | ~ ( S ) ~ | ~ \ varepsilon } . Juga, kebanyakan ekspresi aritmatika yang dihasilkan oleh tata bahasa bebas konteks

Contoh :

Bahasa bebas konteks pola dasar adalah {\ displaystyle L = \ {a ^ {n} b ^ {n}: n \ GEQ 1 \}}, bahasa semua non-kosong string bahkan panjang, seluruh pertama bagian dari yang {\ displaystyle sebuah} ‘s, dan seluruh bagian kedua yang {\ displaystyle b}’ s. {\ Displaystyle L} dihasilkan oleh tata bahasa {\ displaystyle S \ ke ASB ~ | ~ ab}. Bahasa ini tidak biasa. Hal ini diterima oleh otomat pushdown {\ displaystyle M = (\ {Q_ {0}, Q_ {1}, Q_ {f} \}, \ {a, b \}, \ {a, z \}, \ delta , Q_ {0}, z, \ {Q_ {f} \})} dimana {\ displaystyle \ delta} didefinisikan sebagai berikut: [catatan 1]

{\ Displaystyle \ delta (Q_ {0}, a, z) = (Q_ {0}, az)}

{\ Displaystyle \ delta (Q_ {0}, a, a) = (Q_ {0}, aa)}

{\ Displaystyle \ delta (Q_ {0}, b, a) = (Q_ {1}, \ varepsilon)}

{\ Displaystyle \ delta (Q_ {1}, b, a) = (Q_ {1}, \ varepsilon)}

CFL ambigu adalah subset yang tepat dari semua CFL: ada CFL inheren ambigu. Contoh dari CFL inheren ambigu adalah gabungan dari {\ displaystyle \ {a ^ {n} b ^ {m} c ^ {m} d ^ {n} | n, m> 0 \}} dengan {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} d ^ {m} | n, m> 0 \}}. set ini bebas konteks, karena penyatuan dua bahasa bebas konteks selalu bebas konteks. Tapi tidak ada cara untuk tegas mengurai string dalam (non-bebas konteks) bagian {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | n> 0 \} } yang merupakan persimpangan dua bahasa tersebut.

Set { \ displaystyle \ {a ^ { n } b ^ { n } c ^ { n } d ^ { n } | n > 0 \ } } adalah bahasa konteks – sensitif , tapi ada tidak ada konteks bebas tata menghasilkan bahasa ini . [ 2 ] Jadi di sana ada bahasa konteks – sensitif yang tidak bebas konteks . Untuk membuktikan bahwa bahasa yang diberikan tidak bebas konteks , seseorang dapat menggunakan lemma memompa untuk bahasa bebas konteks atau sejumlah metode lain, seperti Ogden lemma atau teorema Parikh ini .

bahasa bebas konteks ditutup di bawah operasi berikut . Artinya, jika L dan P adalah bahasa bebas konteks , bahasa berikut ini adalah bebas konteks juga:

serikat { \ displaystyle L \ secangkir P } L dan P

pembalikan L

Rangkaian { \ displaystyle L \ cdot P } L dan P

tanda star { \ displaystyle L ^ { * } } L

gambar { \ displaystyle \ varphi ( L ) } dari L di bawah homomorfisma sebuah { \ displaystyle \ varphi }

gambar { \ displaystyle \ varphi ^ { – 1 } ( L ) } dari L di bawah homomorfisma terbalik { \ displaystyle \ varphi ^ { – 1 } }

pergeseran siklik dari L ( bahasa { \ displaystyle \ { vu : uv \ di L \ } } )

bahasa bebas konteks tidak tertutup di bawah pelengkap , persimpangan , atau perbedaan .

Namun, jika L adalah bahasa bebas konteks dan D adalah bahasa reguler maka kedua persimpangan mereka { \ displaystyle L \ cap D } dan perbedaan mereka { \ displaystyle L \ setminus D } adalah bahasa bebas konteks .

Nonclosure bawah persimpangan , pelengkap , dan perbedaan [ sunting ]

Bahasa bebas konteks tidak tertutup di bawah persimpangan . Hal ini dapat dilihat dengan mengambil bahasa { \ displaystyle A = \ {a ^ { n } b ^ { n } c ^ { m } \ pertengahan m , n \ GEQ 0 \ } } dan { \ displaystyle B = \ { a ^ { m } b ^ { n } c ^ { n } \ pertengahan m , n \ GEQ 0 \ } } , yang keduanya bebas konteks . [catatan 2 ] persimpangan mereka adalah { \ displaystyle A \ cap B = \ { a ^ { n } b ^ { n } c ^ { n } \ pertengahan n \ GEQ 0 \ } } , yang dapat ditunjukkan untuk menjadi non – konteks bebas oleh lemma memompa untuk bahasa bebas konteks .

bahasa bebas konteks juga tidak tertutup di bawah komplementasi , seperti untuk bahasa apa A dan B : { \ displaystyle A \ cap B = { \ overline { { \ overline { A} } \ cup { \ overline { B } } } } } .

Bebas konteks bahasa juga tidak tertutup di bawah perbedaan : LC = Σ * \ L

PDA (Push down automata)

Dalam ilmu komputer, sebuah robot pushdown (PDA) adalah jenis robot yang mempekerjakan stack.

automata pushdown digunakan dalam teori tentang apa yang dapat dihitung oleh mesin. Mereka lebih mampu dari mesin finite-state tetapi kurang mampu dari mesin Turing. Deterministik pushdown automata dapat mengenali semua bahasa bebas konteks deterministik sementara yang nondeterministic dapat mengenali semua bahasa bebas konteks. Terutama mantan digunakan dalam desain parser.

Istilah “pushdown” mengacu pada fakta bahwa tumpukan dapat dianggap sebagai yang “didorong ke bawah” seperti dispenser nampan di kantin, karena operasi tidak pernah bekerja pada unsur-unsur lain dari elemen atas. Sebuah robot tumpukan, sebaliknya, tidak memungkinkan akses dan operasi pada elemen yang lebih dalam. Stack automata dapat mengenali satu set ketat lebih besar dari bahasa dari pushdown automata. [1] Sebuah bersarang tumpukan otomat memungkinkan akses penuh, dan juga nilai-nilai memungkinkan ditumpuk menjadi seluruh sub-tumpukan bukan hanya simbol yang terbatas tunggal.

Sisa dari artikel ini menjelaskan pushdown otomat nondeterministic.

automata pushdown berbeda dari mesin negara yang terbatas dalam dua cara:

Mereka dapat menggunakan bagian atas tumpukan untuk menentukan transisi untuk mengambil.

Mereka dapat memanipulasi stack sebagai bagian dari melakukan transisi.

automata pushdown memilih transisi dengan mengindeks meja dengan sinyal input, kondisi saat ini, dan simbol di bagian atas tumpukan. Ini berarti bahwa ketiga parameter benar-benar menentukan jalur transisi yang dipilih. mesin negara yang terbatas hanya melihat sinyal masukan dan keadaan saat: mereka tidak memiliki tumpukan untuk bekerja dengan. automata pushdown menambahkan stack sebagai parameter untuk pilihan.

automata pushdown juga dapat memanipulasi stack, sebagai bagian dari melakukan transisi. mesin negara yang terbatas memilih negara baru, hasil berikut transisi. manipulasi dapat mendorong simbol tertentu ke puncak stack, atau pop dari atas tumpukan. otomat alternatif bisa mengabaikan stack, dan biarkan seperti itu. Pilihan manipulasi (atau tidak ada manipulasi) ditentukan oleh tabel transisi.

Disatukan: Mengingat sinyal input, kondisi saat ini, dan simbol tumpukan, otomat dapat mengikuti transisi ke negara bagian lain, dan secara opsional memanipulasi (push atau pop) stack.

Secara umum, pushdown automata mungkin memiliki beberapa perhitungan pada string masukan yang diberikan, beberapa di antaranya dapat menghentikan dalam konfigurasi menerima. Jika hanya satu perhitungan ada untuk semua string yang diterima, hasilnya adalah pushdown robot deterministik (DPDA) dan bahasa string ini adalah bahasa bebas konteks deterministik. Tidak semua bahasa bebas konteks yang deterministik. [2] Sebagai konsekuensi dari atas DPDA adalah varian ketat lemah dari PDA dan tidak terdapat algoritma untuk mengkonversi PDA ke DPDA setara, jika seperti DPDA ada.

Jika kita membiarkan akses robot yang terbatas untuk dua tumpuk, bukan hanya satu, kita mendapatkan perangkat yang lebih kuat, setara dalam kekuatan untuk mesin Turing. Sebuah linear dibatasi robot adalah perangkat yang lebih kuat daripada robot pushdown tapi kurang daripada mesin Turing.

DAFTAR PUSTAKA

http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda/

https://www.academia.edu/25461705/Push_down_automata