编译原理NFAM

‘壹’ 编译原理课程设计:从NFA构造与之等价的正规式r的程序实现

NFA，DFA要画图，不会画图啊！

‘贰’ 编译原理的课程设计，构造正规式r*（闭包运算）的NFA的程序实现。求源代码，求文档。 谢谢

个人感觉画出NFA最直观易懂了。前一个正规式仅有一个状态（开始和接受状态同），后一个虽然是三个状态，但是其中一个是绕着a闭包的状态，一个是绕着b闭包的状态，而这两个状态又是绕着第三状态（既是开始状态又是接受状态）进行闭包，所以实际上可合并为一种状态，即是说这两个正规式对应于同一个NFA，所以相等是显然成立的。

‘叁’ ！！编译原理DFA和NFA

DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

‘肆’ 对给定的正规式b(a|b)*aa,构造其NFA M，并将其确定化。

表示方法：五元组（S，Z，f，S0，z）

S：状态集

Z：字母表

f：映射关系

s0：初态

z：终态

（2）确定有限自动机DFA：f为单值映射

（3）非确定有限自动机NFA：f为多值映射

（4）状态转换图和状态转换矩阵

(4)编译原理NFAM扩展阅读

假定DFAMd＝（｛s0，s1，s2｝，｛a，b｝，f，s0，｛s2｝）：

f：

f（s0，a）＝s1f（s0，b）＝s2

f（s1，a）＝s1f（s1，b）＝s2

f（s2，a）＝s2f（s2，b）＝s1

试着给出Md的状态转换图和状态转换矩阵。

状态转换矩阵如下

ab

s0s1s2

s1s1s2

s2s2s1

‘伍’ 编译原理，如何判断一个FA是DFA还是NFA

第一个是NFA 第二个是DFA
主要区别
1）DFA没有输入空串之上的转换动作；
2）对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集；

‘陆’ 一个关于编译原理的很难的问题

NFA据说要画图的画表的。。。这里可以么？

‘柒’ 编译原理判断题 设M是一个NFA,并且L(M)={x,y,z},则M的状态数至少为4个 请问这句话为什么是错误的呢

M的状态数至少为4个，这句话不正确。

比如下图，同样符合题目条件，但状态只有2个。

‘捌’ 计算机编译原理什么是NFA

ε只能出现在NFA中，当然不是为了方便直观，而是连通NFA和DFA的桥梁。编译原理讲授的不是如何绘制NFA或者DFA，二是告诉读者怎样能够自动实现NFA或DFA的构造。在实际应用中ε可以帮助计算机转换NFA为DFA，而在属性文法和语法制导阶段，它也是沟通综合属性与继承属性、执行语义动作不可或缺的一部分。另外ε的使用可以大大简化文法产生式的构造难度。我记得最初使用ε是为了使得文法体系（字母表）更加完善，但是在实际应用中却变得应用广泛(此观点不一定正确)。最后想说的是，在编译中，ε也带来了不小的麻烦，否则也就不会有诸如“去空产生式”这样的算法了:)

‘玖’ 如题，编译原理中为什么要将NFA转化为DFA

对DFA来说，一个输入必然对应唯一的路径与结果，而这正是我们设计编译器所需要的。

如果从一个状态经过同样的一个输入可以通过两条或更多路径达到不同的状态，我们的编译器就会迷惑（不知道怎么办），只能通过穷举测试每个状态是否可行，而穷举算法的效率通常都很低下。
DFA的最简化是有固定算法的，NFA有没有我不知道，通常最简化之后的DFA要比NFA简单得多

‘拾’ 编译原理中为什么要将NFA转化为DFA

编译原理中DFA是确定的有限自动机，而NFA是非确定有限自动机，将NFA化为DFA是将状态数减少，更为简单确定
希望能给你帮助。