编译原理_NFA-＞DFA 子集法
文章目录 求解五元组 视频讲解DFA和NFA的等价性 NFA转换为DFA 转换表实例1例子 2 例子3: 识别无符号数的DFA例子4例子5 更多例子
NFA等价的DFA子集法求解 NFA
一个不确定的有穷自动机 M 是一个五元组:
M = ( K , Σ , f , S , Z ) M=(K, \Sigma, f, S, Z) M=(K,Σ,f,S,Z)
其中:
(1) K K K 是一个有穷集, 它的每个元素称为一个状态。
(2) Σ \Sigma Σ 是一个有穷字母表, 它的每个元素称为一个输人符号。
(3) f f f 是一个从 K × Σ ∗ K \times \Sigma^{*} K×Σ∗到 K K K 的全体子集的映像, 即 K × Σ ∗ → 2 K K \times \Sigma^{*} \ 2^{K} K×Σ∗→2K , 其中 2 K 2^{K} 2K 表示 K K K 的 幂集。
(4) S ⊆ K S \ K S⊆K , 是一个非空初态集。
(5) Z ⊆ K Z \ K Z⊆K , 是一个终态集。
一个含有m个状态和n 个输人符号的NFA可表示成一张状态转换图,
这张图含有m个状态结点,每个结点可射出若干条箭弧与别的结点相连接,
每条弧用 ∑ ∗ \sum^* ∑∗中的一个串作标记,整个图至少含有一个初态结点以及若干个终态结点。
DFA(NFA的特例)
( 1 ) K 是 一 个 有 穷 集 , 它 的 每 个 元 素 称 为 一 个 状 态 。 ( 2 ) Σ 是 一 个 有 穷 字 母 表 , 它 的 每 个 元 素 称 为 一 个 输 人 符 号 , 所 以 也 称 Σ 为 输 人 符 号 表 。 ( 3 ) f 是 转 换 函 数 , 是 K × Σ → K 上 的 映 像 。 例 如 , f ( k i , a ) = k j ( k i ∈ K , k j ∈ K ) , 就 意 味 着 , 当 前 状 态 为 k i 、 输 人 字 符 为 a 时 , 将 转 换 到 下 一 状 态 k 1 , 把 k j 称 作 k i 的 一 个 后 继 状 态 。 ( 4 ) S ∈ K , 是 唯 一 的 一 个 初 态 。 ( 5 ) Z ⊆ K , 是 一 个 终 态 集 , 终 态 也 称 可 接 受 状 态 或 结 束 状 态 。 (1) K 是一个有穷集, 它的每个元素称为一个状态。\\ (2) \Sigma 是一个有穷字母表,它的每个元素称为一个输人符号, 所以也称 \Sigma 为输人符 号表。\\ (3) f 是转换函数, 是 K \times \Sigma \ K 上的映像。\\例如, f\left(k_{i}, a\right)=k_{j}\left(k_{i} \in K, k_{j} \in K\right) , \\ 就意味 着, 当前状态为 k_{i} 、输人字符为 a 时, 将转换到下一状态 k_{1} , 把 k_{j} 称作 k_{i} 的一个后继状态。\\ (4) S \in K , 是唯一的一个初态。\\ (5) Z \ K , 是一个终态集, 终态也称可接受状态或结束状态。\\ (1)K是一个有穷集,它的每个元素称为一个状态。(2)Σ是一个有穷字母表,它的每个元素称为一个输人符号,所以也称Σ为输人符号表。(3)f是转换函数,是K×Σ→K上的映像。例如,f(ki,a)=kj(ki∈K,kj∈K),就意味着,当前状态为ki、输人字符为a时,将转换到下一状态k1,把kj称作ki的一个后继状态。(4)S∈K,是唯一的一个初态。(5)Z⊆K,是一个终态集,终态也称可接受状态或结束状态。
正则表达式构造NFA 基础对应关系 ε对应的NFA
字母表Σ中符号a对应的NFA
连接&或&幂运算对应的NFA
求解五元组
欲求NFA N等价的DFA M,需要求出对应的DFA M的五元组
两种运算
ε − c l o s u r e 运 算 \-运算 ε−运算和 m o v e move move运算
(2）状态集合Ⅰ的α弧转换,表示为 m o v e ( I , a ) move(I,a) move(I,a),
我们把下文用到的符号捋一下:
算法伪代码
本图中,不确定有穷状态机N的有限状态集K包括了0,1,…10 这11种状态.;
且,状态 K 0 K_0 K0是状态0
子集族C要表达的意思和S相近,C可能强调顺序
回顾求解子集算法
算法为二重循环
中的内层循环(for)是对输入符号集合(字母表)做遍历
m o v e ( S t a t e S e t , a ) move(,a) move(,a)都是找出某一出边(弧)的过程前者是找 ε \ ε(可以连续多次的);后者是找输入符号a(不可连续)手工计算的时候,可以使用树形分叉记法(习惯看表格的话叶可以将状态转移图转化成状态转移表,然后再画树状分支,注意 ε − c l o s u r e \- ε−运算包含起点本身) 视频讲解 DFA和NFA的等价性 NFA&DFA&FA&正则 带有ε边的NFA
带不带空边(ε边)的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的各个状态节点,将出边标出
回顾转移函数的定义
收获五元组
在计算子集的时候,可以将过程用表格的形式记录,这会方便于整理转换函数的总结
