编译原理_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