Push Down Automata

Struktur Dasar PDA

Automat pushdown adalah cara untuk menerapkan tata bahasa bebas konteks dengan cara yang sama kita merancang DFA untuk tata bahasa biasa. DFA dapat mengingat sejumlah informasi yang terbatas, tetapi PDA dapat mengingat jumlah informasi yang tak terbatas.

Pada dasarnya otomat pushdown adalah -

"Mesin negara terbatas" + "setumpuk"

Automat pushdown memiliki tiga komponen -

• rekaman input,
• unit kontrol, dan
• tumpukan dengan ukuran tak terbatas.

Kepala tumpukan memindai simbol atas tumpukan.

Tumpukan melakukan dua operasi -

• Push - simbol baru ditambahkan di bagian atas.
• Pop - simbol teratas dibaca dan dihapus.

PDA mungkin atau mungkin tidak membaca simbol input, tetapi harus membaca bagian atas tumpukan di setiap transisi.

PDA dapat secara resmi digambarkan sebagai 7-tupel (Q, ∑, S, δ, q 0 , I, F) -

• Q adalah jumlah negara terbatas
• ∑ adalah alfabet input
• S adalah simbol stack
• δ adalah fungsi transisi: Q × (ε ∪ {ε}) × S × Q × S *
• q 0 adalah kondisi awal (q 0 ∈ Q)
• I adalah simbol stack top awal (I ∈ S)
• F adalah seperangkat status penerimaan (F ∈ Q)

Diagram berikut menunjukkan transisi dalam PDA dari keadaan q 1 ke keadaan q 2 , dilabeli sebagai a, b → c -

Ini berarti pada status q 1 , jika kita menemukan string input 'a' dan simbol teratas dari stack adalah 'b' , maka kita pop 'b' , tekan 'c' di atas stack dan pindah ke status q 2 .

Terminologi Terkait dengan PDA

Deskripsi sesaat

Deskripsi instan (ID) PDA diwakili oleh triplet (q, w, s) di mana

• q adalah negara
• w adalah input yang tidak digunakan
• s adalah isi stack

Notasi Turnstile

Notasi "turnstile" digunakan untuk menghubungkan pasangan ID yang mewakili satu atau banyak gerakan PDA. Proses transisi dilambangkan dengan simbol pintu putar "⊢".

Pertimbangkan PDA (Q,, S, δ, q 0 , I, F). Transisi dapat secara matematis diwakili oleh notasi turnstile berikut -

(p, aw, Tβ) ⊢ (q, w, αb)

Ini menyiratkan bahwa saat mengambil transisi dari keadaan p ke keadaan q , simbol input 'a' dikonsumsi, dan bagian atas tumpukan 'T' diganti oleh string baru 'α' .

Catatan - Jika kita menginginkan nol atau lebih gerakan dari PDA, kita harus menggunakan simbol (⊢ *) untuk itu Ada dua cara berbeda untuk mendefinisikan penerimaan PDA.

Penerimaan Keadaan Akhir

Dalam keadaan penerimaan terakhir, PDA menerima string ketika, setelah membaca seluruh string, PDA berada dalam keadaan akhir. Dari kondisi awal, kita dapat membuat gerakan yang berakhir pada kondisi akhir dengan nilai stack apa pun. Nilai tumpukan tidak relevan selama kita berakhir dalam keadaan akhir.

Untuk PDA (Q, ∑, S, δ, q 0 , I, F), bahasa yang diterima oleh himpunan status akhir F adalah -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}

untuk setiap string tumpukan input x .

Penerimaan Stack Kosong

Di sini PDA menerima string ketika, setelah membaca seluruh string, PDA telah mengosongkan tumpukannya.

Untuk PDA (Q, ∑, S, δ, q 0 , I, F), bahasa yang diterima oleh tumpukan kosong adalah -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}

Contoh

Bangun PDA yang menerima L = {0 n 1 n | n ≥ 0}

Larutan

Bahasa ini menerima L = {ε, 01, 0011, 000111, .............................}

Di sini, dalam contoh ini, jumlah 'a' dan 'b' harus sama.

• Awalnya kami menaruh simbol khusus '$' ke tumpukan kosong.
• Kemudian pada kondisi q 2 , jika kita menemukan input 0 dan top adalah Null, kita dorong 0 ke stack. Ini mungkin berulang. Dan jika kita menjumpai input 1 dan top adalah 0, kita letakan 0 ini.
• Kemudian pada status q 3 , jika kita menemukan input 1 dan top adalah 0, kita beri tanda 0. Ini juga dapat diulang. Dan jika kita menjumpai input 1 dan atas adalah 0, kita meledakkan elemen atas.
• Jika simbol khusus '$' ditemukan di atas tumpukan, itu muncul dan akhirnya pergi ke negara penerima q 4 .

Contoh

Bangun PDA yang menerima L = {ww R | w = (a + b) *}

Larutan

Awalnya kami menaruh simbol khusus '$' ke tumpukan kosong. Pada kondisi q 2 , w sedang dibaca. Dalam kondisi q 3 , setiap 0 atau 1 muncul ketika cocok dengan input. Jika ada input lain yang diberikan, PDA akan mati. Ketika kita mencapai simbol khusus '$', kita pergi ke negara penerima q 4 .

Referensi :

https://www.tutorialspoint.com/automata_theory/pushdown_automata_introduction.htm