99问答网
所有问题
编译原理中,由NFA转化来的DFA是唯一的吗?
如题所述
举报该问题
推荐答案 2014-03-22
根据算法转化来的DFA肯定是唯一的,但是转化得到的DFA并不一定是状态最少的,每一个DFA都可以转化到状态最少的DFA。状态最少的DFA是唯一的(状态名不同的同构情况除外)。可参考龙书(一本编译书籍)。因为每个DFA都可以对应相应的NFA(DFA本身就是),所以NFA转化的DFA不一定都是状态数最少的。
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://99.wendadaohang.com/zd/XezjWvW7WvvXjeXBXv.html
相似回答
编译原理中
确定的有穷自动机和不确定的有穷自动机有什么区别?
答:
确定的有穷自动机就是说当一个状态面对一个输入符号的时候,它所转换到的是一个唯一确定的状态;而不确定的有穷自动机是说当一个状态面对一个输入符号的时候,它所转换到的可能不只一个状态,可以是一个状态集合.这就是两者的主要区别.还有就是
DFA
的开始状态
是唯一的,
而
NFA的
开始状态是一个开始状态集...
编译原理NFA
转DFA 请问
DFA的
初始状态如何
答:
DFA的终态就是所有包含了NFA终态
的DFA的
状态 就如下边的例子,是一个初态为1,终态为6,7,9的NFA经过确定化得到的转换矩阵,右侧是将左侧的转换矩阵改名之后
的DFA,
也就是最后得到的DFA 对于DFA来说,他的初态就是包含了
NFA唯一
初态1的那个状态,就是左边的1,2右边的1了 终态则是左边的2,...
如题
,编译原理中
为什么要将
NFA转化为DFA
答:
对
DFA
来说,一个输入必然对应
唯一的
路径与结果,而这正是我们设计
编译
器所需要的。如果从一个状态经过同样的一个输入可以通过两条或更多路径达到不同的状态,我们的编译器就会迷惑(不知道怎么办),只能通过穷举测试每个状态是否可行,而穷举算法的效率通常都很低下。DFA的最简化是有固定算法的
,NFA
有没...
编译原理,
如何判断一个
FA是DFA
还是
NFA
答:
第一个是
NFA
第二个是DFA 主要区别 1)DFA没有输入空串之上的转换动作;2)对于
DFA,
一个特定的符号输入,有且只能得到一个状态,而NFA就有可能得到一个状态集;
编译原理 中
nfa
dfa
的初始状态和终止状态可以是一个吗 小弟求大神指...
答:
可以的,初始状态和结束状态完全可以是一个!(a|b)*这个语言就可以写成初始状态和结束状态为一个状态的形式。
!!
编译原理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时,...
正则表达式概述 什么是正则表达式
答:
automaton,简称
DFA
)。其实,正则表达式是一个不确定有限自动机。NFA和DFA的最大区别在于它们的状态转换函数。NFA可以对同一个字符串产生多种理解方式,而DFA则只有
唯一的
一种理解方式。也正因为如此,NFA在匹配过程中可能会回溯
,NFA的
效率一般要低于DFA。因此,在书写正则表达式时尽量减少回溯来提高正则...
编译原理中
为什么要将
NFA转化为DFA?
答:
编译原理中DFA是
确定的有限自动机,而
NFA
是非确定有限自动机,将NFA化为DFA是将状态数减少,更为简单确定
【
编译原理
】第三章:词法分析
答:
从人的角度看
,NFA
比DFA更加直观;但对于程序来说,DFA比NFA容易实现。直接从RE转换到
DFA是
比较困难的,所以一般通过NFA作为中介。DFA中的每个状态都是NFA中状态集合的一个子集。即,先写出
NFA的
转换表,再通过新的状态构建出DFA。例:记数字为 ,字母为 ,那么标识符的正则表达式为:这个正则表达式...
大家正在搜
编译原理局部优化中常用的优化方法
编译原理中的句柄是什么
编译原理中的箭头是什么意思
编译原理中什么是产生式
编译原理中的语言
从实战中理解编译原理
编译原理中的闭包
编译原理中扫描器是什么
编译原理中first集的求法
相关问题
编译原理中的dfa是什么意思,是什么术语的缩写?
请问编译原理中为什么要将NFA转化为DFA?
nfa如何转换成等价的dfa结果唯一吗
编译原理,子集法将NFA确定为DFA,求问,表格中的部分都是...
编译原理NFA转DFA ,请问DFA的初始状态如何确定?
!!编译原理DFA和NFA
编译原理:怎样用c语言实现nfa到dfa转化及优化
编译原理:怎么用子集法将NFA转换成DFA? 用图4.16的...