PUSH DOWN AUTOMATA
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”.
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.
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.
PDA Deterministik
PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T x ∈ (a b)*}, dimana = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : δ(q 0 , a, Z 0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input c. Pada stata q 1 PDA akan melakukan POP.
PDA Non-Deterministik
PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (a b)*} mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b}, = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika
mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input ε. Pada stata q 1 PDA akan melakukan POP. Contoh menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.
Daftar Pustaka
Oktaria, Resalina. 2016. Push Down Automata (Ekivalensi PDA dan CFG serta deterministic PDA). diakses dari http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda, pada 6 Maret 2020.
Juarna, Asep. 2003. TEORI BAHASA DAN AUTOMATA. diakses dari http://didi.staff.gunadarma.ac.id/Downloads/folder/0.0.3, pada 6 Maret 2020.
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.
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.
PDA Deterministik
PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T x ∈ (a b)*}, dimana = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
PDA Non-Deterministik
PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (a b)*} mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b}, = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input ε. Pada stata q 1 PDA akan melakukan POP. Contoh menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.
Daftar Pustaka
Oktaria, Resalina. 2016. Push Down Automata (Ekivalensi PDA dan CFG serta deterministic PDA). diakses dari http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda, pada 6 Maret 2020.
Juarna, Asep. 2003. TEORI BAHASA DAN AUTOMATA. diakses dari http://didi.staff.gunadarma.ac.id/Downloads/folder/0.0.3, pada 6 Maret 2020.
0 comments:
Post a Comment