Ubah CFG menjadi PDA

9

Apakah ada seperangkat aturan atau metode untuk mengubah tata bahasa bebas konteks apa pun menjadi automata push down?

Saya sudah menemukan beberapa slide online tetapi saya tidak dapat memahaminya.

Dalam slide 10 dia berbicara tentang beberapa aturan, adakah yang bisa menjelaskannya?

context-free formal-grammars pushdown-automata simulation makaka
sumber
2
periksa wikipedia, dan pertanyaan ini . Idenya adalah untuk menghasilkan kata (menggunakan tata bahasa) pada stack, dan mencocokkannya dengan input. Triknya adalah melakukannya secara paralel - menghasilkan bagian dari kata, memeriksanya, menghasilkan lebih banyak, memeriksanya, dll.
Ran G.
2
Sebuah video yang membahas topik ini, dan mudah dimengerti: youtube.com/watch?v=MJ9xNavURY8
Ran G.

Jawaban:

1

Aturan aktual untuk konstruksi ini diberikan pada slide 7 dalam presentasi ini. Wikipedia menyebut aturan ini "cocok" dan "perluas".

Slide yang Anda gunakan berasal dari kursus oleh Jeff Ullman tampaknya. (Salah satu penulis buku terkenal tentang bahasa formal dan automata). Dia juga telah menyiapkan kursus online tentang topik tersebut, di mana saya kira dia akan menjelaskan rinciannya sendiri.

Hendrik Jan
sumber