【形式语言与自动机/编译原理】CFG--＞Greibach--＞NPDA（2）

本文将详细讲解《形式语言与自动机》（研究生课程）或《编译原理》（本科生课程）中的上下文无关文法（CFG）转换成Greibach范式，再转成下推自动机（NPDA）识别语言是否可以被接受的问题。此外，本文还给出了python代码的具体实现。

由于内容比较多，所以为了讲清楚，分成了3篇博客，第一篇主要讲 解从上下文无关文法到Greibach范式的具体步骤和流程，并给出了相应的算法及具体的例子；第二篇（即本篇）主要讲解从Greibach范式到下推自动机NPDA，同样给出了相应的算法及具体的例子；第三篇主要是对前两篇中给出的算法用python语言进行实现，并测试之前的例子。

它们的地址如下：

第一篇：

第二篇：

第三篇：

---

2 由Greibach范式得到下推自动机NPDA

2.1 生成状态转移函数

以下给出3个例子：

2.2 得到下推自动机NPDA

针对这个Greibach范式和状态转移函数，给出4个测试例子：

---

以上就是本文的内容，主要介绍了由Greibach范式得到下推自动机NPDA的各个步骤，下一篇将根据之前给出的算法用python语言进行实现。