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

2023-12-31 16:31:57

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

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

它们的地址如下：

第一篇：

第二篇：

第三篇：

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

2.1 生成状态转移函数

1126853e7bc6481ca058e8e2ff3eeaaa.png

eb1e426536354924ac6736db8398d9a2.png

a732275190f34b2b8e5356f31167b38e.png

以下给出3个例子：

a0870b00df804944ae250a23fcb6d899.png

66d1c97f166c476f976a8a16697ccb60.png

326b0a69e9d54d0fb6ac503c1b777ac9.png

2.2 得到下推自动机NPDA

ef6e377e6dd14cb59fa77db698ed08f1.png

7a2520186f174db9aa517b1d0028930d.png

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

2a8f8bf1ff014454908f362927c7e927.png

702ed71f719643508417775afc87fdc9.png

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

?

文章来源:https://blog.csdn.net/m0_56367027/article/details/135313468
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。