编译原理_NFA-＞DFA 子集法( 二 ) _符号

带不带空边(ε边)的NFA间具有等价性
根据RE(正则表达式)构造NFA ε对应的NFA
字母表Σ中符号a对应的NFA
案例:
NFA转换为DFA NFA与DFA的对比
DFA与NFA的等价性
move运算(和字母表(输入字符)有关)
千万记住,move(I,a)运算的结果 J a J_a Ja?只是一个中间结果,想要得到转换表中的 I a I_a Ia?,还必须要再次执行ε运算对于其他字母表中的字母(例如b,c,d,…),也是类似的流程
字母状态转换表中的Ia,Ib,Ic,…取决于文法的字母表总符号的个数
一个容易出错/疏漏的地方在于,被执行ε运算的状态(集)本身也要加入到ε计算的结果集合中,
或者说,本身集合中的元素至少要加入到ε-的结果集合中)(因为,我们允许经过的ε的弧数为0)
状态转换表
转换表实例1
DFA是NFA的特例
例子 2 没有ε边的

文章插图
当然,新的状态集合来自于状态转换表中的非空状态集,可以单独将他们整理出来,得到以下的DFA状态转换图
从带有ε-边的NFA到DFA的转换
需要注意的是,终止状态的判断,转换为DFA的每次新产生的一个状态都需要判断该状态(集合)中是否含有NFA的终止态(之一)
例子3: 识别无符号数的DFA
分析完输入符号集后,将状态集合中的每个状态分别尝试这些可能的输入,在最多的情况下,产生的新状态集可达到x*y个
容易出错的两个方面
例子4
例子5
可以围绕这FA的各个状态节点,将出边标出
回顾转移函数的定义
收获五元组
【编译原理_NFA-＞DFA 子集法】在计算子集的时候,可以将过程用表格的形式记录,这会方便于整理转换函数的总结