NFA如何转换成等价的DFA_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
NFA如何转换成等价的DFA
&&NFA如何换成等价的DFA
大小：1.16MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢博客访问： 146749
博文数量： 28
博客积分： 1205
博客等级： 少尉
技术积分： 180
注册时间：
codeqq的ChinaUnix博客
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
{q1,q2,…qk}
L(M1)=L(M2)
阅读(10685) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。计算理论：NFA转DFA的两种方法 - CSDN博客
计算理论：NFA转DFA的两种方法
本文将以两种方法实现NFA转DFA，并利用C语言实现。
方法二已利用HNU OJ系统验证，方法一迷之WA，但思路应该是对的，自试方案，测试均通过。
（主要是思路，AC均浮云，大概又有什么奇怪的Case没想到）
==========================================================
下面的描述以机械工业出版社的《计算理论导引》的第三版35页图为例。该NFA如下图。
思路一：穷举组合状态，构造DFA
该思路接近《计算理论》课本35页思路。
新DFA的状态数
为了能够保存NFA的各种不确定状态，DFA利用更多的状态来模拟保存。假设NFA有N个状态，那么每一个状态都有到达和没有到达两种可能，也就是新的DFA有2^N个新的状态。例如当我们到达上图中的状态1时，由于存在空漂移，那么我们可能到达了3状态，也就是新DFA状态中的101(5)号状态。
先把这种思路的核心代码放在下面：
int find_next(int CurrState,int* NextStateArray,int NFA_size){
int NextState = 0,i = 0,NFAState = 0;
for(i = NFA_size-1; i&=0;i--){
NFAState = CurrState/(1&&i);
CurrState -= NFAState * (1&&i);
if(NFAState == 1) NextState = NextState|NextStateArray[i];
return NextS
这段代码展现的是思路一、二均使用的核心。以上文提到过的5号(101)状态来举例。
currstate = 5(101)的find_next过程
状态号为5(101)代表着该状态包含了原NFA中的状态3和状态1
假设当前输入为0，则传到find_next的参数为转移表中0的那一列:0(000) 6(110) 5(101)
循环中依次访问了101包含的NFA1号状态中的下态(000)和3号状态的下态(101)
通过位或添加到了DFA当前状态的下一个状态中。
当遍历完所有currstate包含的NFA状态，返回统计好的下一状态(101)
find_next函数就是通过这样的方法，对新的DFA中的一个状态在一种输入情况下的状态转移计算出来。获取完整的DFA状态转移，只需要对新的DFA中的所有状态均执行这个过程。（但是这样也就没有考虑一些不可能到达的状态，或可以通过建立后修建得到）
思路二接着刚才的思路一，若我们转成的DFA中有很多很多没有可能到达的状态怎么办？何不逆向考虑，我们从DFA的起始状态开始，推算其有可能达到的DFA状态，判断该状态是否生成。若没有生成，再生成这个DFA新状态。
下面用伪代码来形式化这一个过程。
function define_DFA_state (int currstate)
for currstate 中的每一个包含的NFA状态
currstate 的0输入转移 = 这些NFA状态的0输入转移取位或(思路同find_next)
currstate 的1输入转移 = 这些NFA状态的1输入转移取位或
if currstate 的0输入转移未被定义 define_DFA_state 这个状态
if currstate 的1输入转移未被定义 define_DFA_state 这个状态
end function
这种思路带来的后果是DFA并不是按照0，1，2，3这样排序好的状态，生成状态表的时候可能会顺序比较混乱。记得在代码中重新给状态编号，来更清楚生成状态转移表。
本文已收录于以下专栏：
相关文章推荐
作者：陈梓瀚  (/vczh/)1、问题概述随着计算机语言的结构越来越复杂，为了开发优秀的编译器，人们已经渐渐感到将词 法分析独立出来做研究的重要性。不过词...
在前一篇文章DFA算法的实现与最小化中介绍了DFA,这篇文章将介绍NFA。
1. NFA与DFA的区别
NFA与DFA的主要区别如下:
1) 对于一个特定的符号输入，DFA只会跳转到一个状态；而NFA...
1. 根据上面的状态转换图写出状态转换表，什么！不知道什么是状态转换表？那你来对地方了。状态转换表是转台转换图的另外一种表示形式，如下图，左侧表头0~9表示的
    是状态，上方表头a,b,c表示的...
词法分析中zhongyao
1.历史：引用正则表达式萌芽于1940年代的神经生理学研究，由著名数学家Stephen Kleene第一个正式描述。具体地说，Kleene归纳了前述的神经生理学研究，在一篇题为《正则集代数》的论文中定...
他的最新文章
讲师：王禹华
讲师：宋宝华
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}