编译原理dfa的最简化

① 编译原理由正规式构造DFA

先画出NFA，如图：（我就是传说当中的灵魂画师）

这个DFA本身就已经是最简的了，无法再简化，最简化过程我就直接省了

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

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

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

③ 编译原理--NFA转化为DFA问题 下面是个图，但是最小化后A和C为什么不能合并

看龙书吧，编译上的经典。
怎样实现倒是没有，不过我这里有一个网上淘的简单C语言编译器源码，如果你要我可以发给你。

④ ！！编译原理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表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

⑤ 编译原理这个DFA怎么画

这个是能画的最简单的，左边是开始状态。原则是：1）先连接运算，2）再选择3）再闭包

⑥ 编译原理：高手帮忙看下与正规式等价的状态最少的DFA

http://..com/question/680468671167188732.html?fr=qlquick

⑦ 编译原理中，由NFA转化来的DFA是唯一的吗

根据算法转化来的DFA肯定是唯一的，但是转化得到的DFA并不一定是状态最少的，每一个DFA都可以转化到状态最少的DFA。状态最少的DFA是唯一的（状态名不同的同构情况除外）。可参考龙书（一本编译书籍）。因为每个DFA都可以对应相应的NFA（DFA本身就是），所以NFA转化的DFA不一定都是状态数最少的。

⑧ dfa的最小化如何化简的步骤

下面具体介绍DFA的化简算法：
（1） 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。
K＝K1∪K2
由上述定义知，K1和K2是不等价的。
（2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。
设第i次划分已将状态集划分为k组，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
对于状态集Kj(i)（j=1,2,…,k）中的各个状态逐个检查，设有两个状态Kj’、 Kj’’∈Kj(i)，且对于输入符号a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn属于同一个状态集合，则将Kj’和Kj’’放到同一集合中，否则将Kj’和Kj’’分为两个集合。
（3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。
（4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。
（5） 若有无关状态，则将其删去。
根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。

⑨ 编译原理中，在DFA的最小化问题。

是要分到两个不同集合里的

但是我建议 在极小化时先引入“死状态”
如果一个DFA的转换函数不是全函数，则要引入一个“死状态”sd，sd对所有输入符号都转换到sd本身。
这样你做的时候就会看的很明白

⑩ 编译原理中DFA的终态和非终态怎么区分啊，谁说的通俗点啊

编译原理中DFA的终态和非终态区别为：包含不同、空集不同、状态不同。

一、包含不同

1、DFA的终态：DFA的终态包含了NFA终点结点的状态集合。

2、DFA的非终态：DFA的非终态不包含NFA终点结点的状态集合。

二、空集不同

1、DFA的终态：DFA的终态不可能为空集，因为NFA的终点一定会包含在某个DFA的状态集合中。

2、DFA的非终态：DFA有可能得到的非终态是空集，意味着所有的DFA的状态集合都包含了NFA的终点。

三、状态不同

1、DFA的终态：DFA的终态每个状态之间属于同一个状态。

2、DFA的非终态：DFA的非终态每个状态之间不一定属于同一个状态。