本文將詳細(xì)講解《形式語言與自動機(jī)》（研究生課程）或《編譯原理》（本科生課程）中的上下文無關(guān)文法（CFG）轉(zhuǎn)換成Greibach范式，再轉(zhuǎn)成下推自動機(jī)（NPDA）識別語言是否可以被接受的問題。此外，本文還給出了python代碼的具體實現(xiàn)。

由于內(nèi)容比較多，所以為了講清楚，分成了3篇博客，第一篇主要講 解從上下文無關(guān)文法到Greibach范式的具體步驟和流程，并給出了相應(yīng)的算法及具體的例子；第二篇（即本篇）主要講解從Greibach范式到下推自動機(jī)NPDA，同樣給出了相應(yīng)的算法及具體的例子；第三篇主要是對前兩篇中給出的算法用python語言進(jìn)行實現(xiàn)，并測試之前的例子。

它們的地址如下：

第一篇：

第二篇：

第三篇：

---

2 由Greibach范式得到下推自動機(jī)NPDA

2.1 生成狀態(tài)轉(zhuǎn)移函數(shù)

以下給出3個例子：

2.2 得到下推自動機(jī)NPDA

針對這個Greibach范式和狀態(tài)轉(zhuǎn)移函數(shù)，給出4個測試?yán)?#xff1a;

---

以上就是本文的內(nèi)容，主要介紹了由Greibach范式得到下推自動機(jī)NPDA的各個步驟，下一篇將根據(jù)之前給出的算法用python語言進(jìn)行實現(xiàn)。

?