-
编译原理 | 由正规式构造确定的有穷自动机DFA
2019-04-16 14:51:23词法分析: 由正规式构造确定的有穷自动机DFA 解题方法 1. 先由正规式构造转换系统 规则见下图: 2. 再由转换系统构造确定有穷自动机DFA (1) 求 Ia 假定 I 是转换图状态集 K 一个子集,Ia 是 I 中状态经历 一条 a...词法分析
: 由正规式构造确定的有穷自动机DFA解题方法
1. 先由正规式构造转换系统
规则见下图:
2. 再由转换系统构造确定有穷自动机DFA
(1) 求 Ia
假定 I 是转换图状态集 K 一个子集,Ia 是 I 中状态经历 一条 a 弧(也可以是 b 弧,看具体题目要求,但必须经过一条),同时可以跳过 a 弧前面和后面的若干 ε 弧,到达的状态集合。
(2) 子集法构造有穷自动机 DFA
- 画表,一共有 2*|∑|+2 列。第一列写 I ,表示状态子集。然后第二列至第 |∑|+1 列,写构造字母表(比如可以经过 a,b,那就第二列写 Ia,第三列写 Ib),然后第 |∑|+2 列,写上“状态”,最后 |∑| 列,写这些构造字母表(用作化简用,比如第五列写 a,第六列写 b)。
- 除去上面的各种列名称,下面开始的第一列第一行,写上初始状态 S 的状态子集 I。
- 针对后面紧跟的 |∑| 列,求相应的 I 子集(例如,Ia 列,就求状态子集 I 经过 求 Ia 后可以到达的状态集合,写入该列)。
- 当求完一行 Ia、Ib 后,把 Ia 和 Ib 中状态子集没有在左侧第一列 I 中出现过的,写入 I 列,重复上一步操作,直到全部出现在左侧第一列 I 中。
- 此时,第 |∑|+2 “状态” 列,从 0 开始标记,直到最后一行。
- 然后,再在最后的 |∑| 列中,根据相应的状态子集对应的数字标记,填写相应数字。
- 根据最后的 |∑|+1 列,画出 DFA 状态转换图。
3. DFA 化简
子集法构造的 DFA 不一定是最简的,往往会有冗余,此时需要化简。
(1) 将状态集划分成互不相交的子集(例如,开始把终态和非终态分开,分成两个子集)。
(2) 再对每个子集重复(1)进行划分,直到不能划分为止(所谓不能划分是指:该子集只有一个状态,或者该子集所有状态已不可再分)。
**注意点:**终态是这样来判断出来的:根据子集法中,最后得出的表,左边第一列,即 I 列中,包含 Z 终止状态的状态子集,都是终态(因为可以到达 Z)。
例题1
构造下列正规式相应的 DFA: (0 | 11*0)*
解:
1. 第一步:构造该正规式的转换系统
2. 第二步:由转换系统构造确定有穷自动机DFA
由上述转换系统可得状态转换集 K={S, 1, 2, 3, 4, Z},状态子集转换矩阵如下表所示:
I I0 I1 K 0 1 {S, 1, Z} {1, Z} {2, 3, 4} 0 1 2 {1, Z} {1, Z} {2, 3, 4} 1 1 2 {2, 3, 4} {1, Z} {3, 4} 2 1 3 {3, 4} {1, Z} {3, 4} 3 1 3 画出转换后的 DFA 状态转换图
3. 第三步:DFA 化简
由状态子集转换矩阵可知,状态 0 和 1 是等价的,而状态 2 和 3 是等价的,因此,合并等价状态之后只剩下 2 个状态,也即是最少状态的 DFA 。
例题2
将 (NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z}),构造相应的 DFA ,其中:M (X, 0) = {Z} M (X, 1) = {X} M (Y, 0) = {X, Y} M (Y, 1) = Ф M (Z, 0) = {X, Z} M (Z, 1) = {Y}
解:
1. 第一步:构造该正规式的转换系统
2. 第二步:由转换系统构造确定有穷自动机DFA
3. DFA 化简
先化简,分为非终态集 {2, 4, 5, 0} 和 终态集 {6, 1, 3},易于发现可划分为 {0,2},{1},{3,6},{4},{5},其 DFA 如下所示
-
剑指 Offer 20. 表示数值的字符串(确定的有穷自动机DFA)
2020-07-16 12:12:46题目 请实现一个函数用来判断字符串是否表示数值...去掉首位空格后建立的自动机,加上空格也可以,只是状态会多出来一个(尾部多出一个识别空格的状态) 小数点前面可以没有数字,对应状态8 小数点后面也可以没有数字,题目
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示数值,但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。
解题思路
下面是DFA:
注:
- 用一个vector内层使用map来保存状态之间的转移。
- 去掉首位空格后建立的自动机,加上空格也可以,只是状态会多出来一个(尾部多出一个识别空格的状态)。
- 小数点前面可以没有数字,对应状态8。
- 小数点后面也可以没有数字,对应状态3为接收状态和3后面直接跟e指数等。
- 接受状态:2、3、4、7。
代码
class Solution { public: bool isNumber(string s) { if(s.size() == 0){ return false; } //运用状态机进行判断 //1.先去掉首尾空格 int n = s.size(); int start = 0; int end = n - 1; //全部是空格的字符串 while(start < n && s[start] == ' '){ ++start; } if(start == n){ return false; } while(end >= 0 && s[end] == ' '){ --end; } //然后用状态机进行判断,一共8个状态: int state = 0; //状态机判断 judge(s, start, end, state); if(state == 2 || state == 3 || state == 4 || state == 7){ return true; } return false; } private: //状态机的9个状态,2、3、4、7是接收状态 //0.初始状态 //1.含有底数前符号+/- //2.小数点前数字 //3.小数点 //4.小数点后数字 //5.e指数 //6.e后面指数的符号 //7.指数的数字 //8.小数点前没有数字 vector<unordered_map<char, int>> myMap; void judge(string s, int start, int end, int &state){ myMap = vector<unordered_map<char, int>>(9); myMap[0] = {{'+', 1}, {'-', 1}, {'d', 2}, {'.', 8}}; //注:小数点前没有数字也符合 myMap[1] = {{'d', 2}, {'.', 8}}; myMap[2] = {{'d', 2}, {'.', 3}, {'e', 5}}; myMap[3] = {{'d', 4}, {'e', 5}}; myMap[4] = {{'d', 4}, {'e', 5}}; myMap[5] = {{'+', 6}, {'-', 6}, {'d', 7}}; myMap[6] = {{'d', 7}}; myMap[7] = {{'d', 7}}; myMap[8] = {{'d', 4}}; for(int i = start; i <= end; ++i){ char c = s[i]; if(c >= '0' && c <= '9'){ //数字 c = 'd'; if(myMap[state].count(c)){ state = myMap[state][c]; } else{ //非法输入,不能进行状态转换,直接将state置为0 state = 0; //0不是接收状态,置为0,然后返回 return; } } else{ if(myMap[state].count(c)){ state = myMap[state][c]; } else{ //非法输入,不能进行状态转换,直接将state置为0 state = 0; //0不是接收状态,置为0,然后返回 return; } } } } };
-
自动机理论、语言和计算导论---有穷自动机:确定型有穷自动机(DFA)
2016-09-07 08:26:40这种自动机在读任何输入序列后只能处在一个状态中 确定型,指的是:在每输入上,存在且仅存在一个状态,自动机可以从当前状态转移到这个状态。...一个确定型有穷自动机包括: 1.一个有穷的状态集合,这种自动机在读任何输入序列后只能处在一个状态中
确定型,指的是:在每输入上,存在且仅存在一个状态,自动机可以从当前状态转移到这个状态。(此处对比非确定型,即可同时处在几个状态中)
NFA与DFA之间的唯一区别在于返回值的类型:在NFA的情况下,返回值是一个状态集合;而在DFA的情况下,返回值是单个状态。
确定型有穷自动机的定义
一个确定型有穷自动机包括:
1.一个有穷的状态集合,通常记作Q
2.一个有穷的输入符号集合,通常记作∑
3.一个转移函数,以一个状态和一个输入符号作为变量,返回一个状态。转移函数通常记作δ
4.一个初始状态q0,是Q中状态之一
5.一个终结状态或接受状态的集合F
DFA五元组:A = (Q,∑,δ,q0,F)
A = {有穷状态集合(条件集合),有穷输入符号集合,转移函数,初始状态,终结状态}
DFA处理串------DFA如何决定是否“接受”输入符号序列
DFA的‘语言’是这个DFA接受的所有的串的集合
例题1.形式化的规定一个DFA,接受所有仅在串中某个地方有01序列的0和1组成的串。
L:{x01y | x和y是0和1的任意串}
对于接受这个语言L的自动机A,可确定一下元组
输入字母表∑ = {0,1}
有穷状态集合Q,其中的一个状态为初始状态
自动机A需要明确:至此看到了什么样的输入。
1.是否已经看到01:如果是,就可接受后续输入的每一个序列,即从现在起只处在接受状态中
2.是否还没看到01,但上一个输入是0,如果现在看到1,那就看到01了。并且由此开始接受输入的所有序列
3.是否还没看到01,但上一个输入要么不存在(刚开始运行),要么上次看到的是1,在这种情况下,A直到先看到0然后理解看到1才接受;
(1)这三个条件每个都能用一个状态来表示。其中,条件3作为初始状态,用q0来表示。因为在刚开始去看是,需要看到一个0然后在看到一个1。但如果在q0状态下先看到一个1,那随后的状态应仍处在q0。即δ(q0,1)= q0
当,在q0状态下先看到0了,那就可以转移至条件2(状态2),此时的状态转移函数记为δ(q0,0)= q2
(2)现在处于状态2,从此刻出发。接下来如果看的的是0,那就相当于仍是处在状态2,即为δ(q2,0)= q2
接下来如果看到的是1,意味着现在已经看到01了,即可转移至条件1(状态1),此时的状态转移函数,即为δ(q2,1)= q1
(3)现在处于状态1,此时已经看到01,意味着无论后续输入什么,都已处于成功的状态,所以此时的状态转移函数,即为(q1,0)= q1,
(q1,1)= q1
分析至此,确定了有穷状态集合Q = {q0,q1,q2}
综上所述,对自动机A的完整描述是:A = ({q0,q1,q2},{0,1},δ,q0,{q1})
-
PHP7系列:词法分析入门-什么是NFA(不确定的有穷自动机)和DFA(确定的有穷自动机)(十)
2020-07-25 22:11:38NFA(不确定有穷自动机) 首先我们来看一个问题:前言
字母表∑1和∑2的乘积( product):
∑1∑2 ={ab|a ∈∑1, b ∈ ∑2}
例: {0, 1} {a, b} ={0a, 0b, 1a, 1b}
字母表∑的n次幂( power):长度为n的符号串构成的集合
∑0 ={ ε }
∑n =∑n-1 ∑ , n ≥例: {0, 1}3 ={0, 1} {0, 1} {0, 1}={000, 001, 010, 011, 100, 101, 110, 111}
字母表的正闭包(positive closure):长度正数的符号串构成的集合:
∑+ = ∑ ∪∑2 ∪∑3 ∪…
例:{a, b, c, d }+ = {a, b, c, d,aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}
字母表的克林闭包(Kleene closure):任意符号串(长度可以为零)构成的集合:
∑* = ∑0 ∪∑+ = ∑0 ∪∑ ∪∑2 ∪∑3 ∪…
例:{a, b, c, d }* = {ε, a, b, c, d,aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}
一、有穷自动机
定义
- 有穷自动机 ( Finite Automata,FA )由两位神经物理学家MeCuloch和Pitts于1948年首先提出,是对一类处理系统建立的数学模型
- 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)
- 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后,系统的内部状态也将发生改变
Finite Automata的典型例子:
- 电梯控制装置
- 输入:顾客的乘梯需求(所要到达的层号)
- 状态:电梯所处的层数+运动方向
- 电梯控制装置并不需要记住先前全部的服务要求,只需要知道电梯当前所处的状态以及还没有满足的所有服务请求
Finite Automata模型示意:
- 输入带(input tape):用来存放输入符号串
- 读头(head ):从左向右逐个读取输入符号,不能修改(只读)、不能往返移动
- 有穷控制器( finite control ):具有有穷个状态数,根据当前的状态和当前输入符号控制转入下一状态
FiniteAutomata的表示:
- 转换图 (Transition Graph)
- 结点:FA的状态
- 初始状态(开始状态):只有一个,由start箭头指向
- 终止状态(接收状态):可以有多个,用双圈表示
- 带标记的有向边:如果对于输入a,存在一个从状态p到状态q的转换,就在p、q之间画一条有向边,并标记上a
Finite Automata定义(接收)的语言:
- 给定输入串x,如果存在一个对应于串x的从初始状态到某个终止状态的转换序列,则称串x被该FA接收
- 由一个有穷自动机M接收的所有串构成的集合称为是该FA定义(或接收)的语言,记为L(M (machine))
最长子串匹配原则(Longest String Matching Principle )
- 当输入串的多个前缀与一个或多个模式匹配时,总是选择最长的前缀进行匹配
- 在到达某个终态之后,只要输入带上还有符号, DFA就继续前进,以便寻找尽可能长的匹配
二、有穷自动机的分类
- 确定的FA (Deterministic finite automata, DFA)
- 非确定的FA (Nondeterministic finite automata, NFA)
确定的有穷自动机DFA(Deterministic Finite Automata)
M = ( S,Σ ,δ,s0,F )
- S:有穷状态集
- Σ:输入字母表,即输入符号集合。假设ε不是 Σ中的元素
- δ:将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态。
- s0:开始状态 (或初始状态),s0∈S
- F:接收状态(或终止状态)集合,F⊆ S
例如下图所展示的一个DFA
非确定的有穷自动机NFA(NonDeterministic Finite Automata)
M = ( S,Σ ,δ,s0,F )
- S:有穷状态集
- Σ:输入符号集合,即输入字母表。假设ε 不是Σ中的元素
- δ:将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态集合
- s0:开始状态 (或初始状态),s0∈S
- F:接收状态(或终止状态)集合,F⊆ S
例如下图所展示的一个NFA
(DFA与NFA的区别在于:如上图用红色方框标出的位置,DFA的每一次输入只对应一个结果,而NFA的依次输入可能对应多个结果,形成一个结果集,后面将使用子集法将NFA构造为DFA)。
3、DFA和NFA的等价性
①
- 对任何非确定的有穷自动机N ,存在定义同一语言的确定的有穷自动机D
- 对任何确定的有穷自动机D ,存在定义同一语言的非确定的有穷自动机N
②
- DFA和NFA可以识别相同的语言(如下图举例所示)
带有“ε-边”的NFA
M = ( S,Σ ,δ,s0,F )
- S:有穷状态集
- Σ:输入符号集合,即输入字母表。假设ε不是Σ中的元素
- δ:将S×(Σ∪{ε})映射到2S的转换函数。s∈S, a∈Σ∪{ε}, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态集合
- s0:开始状态 (或初始状态),s0∈S
- F:接收状态(或终止状态)集合,F⊆ S
带有和不带有“ε-边”的NFA 的等价性
DFA的算法实现
-
输入:以文件结束符eof结尾的字符串x。DFA D 的开始状态s0,接收状态集 F,转换函数move。
-
输出:如果 D接收 x,则回答“yes”,否则回答“no”。
-
方法:将下述算法应用于输入串 x。
s = s0 ; c = nextChar(); while(c! = eof ){ s = move ( s , c ) ; c = nextChar ( ) ; } if (s在F中) return“yes”; else return “no”;
-
函数nextChar( )返回输入串x的下一个符号
-
函数move(s, c)表示从状态s出发,沿着标记为c的边所能到达的状态
三、从正则表达式到有穷自动机
根据RE 构造NFA
- ε对应的NFA
- 字母表Σ中符号a对应的NFA
-
r = r1r2对应的NFA
-
r = r1|r2对应的NFA
- r = (r1)*对应的NFA
例:r=(a|b)*abb 对应的NFA
-
如何将 不确定的有穷自动机(NFA) 转化为 确定的有穷自动机(DFA) 并将DFA最简化...
2019-09-28 23:24:25DFA的每个状态都是一个由NFA中的状态构成的集合,即NFA状态集合的一个子集 r =aa*bb*cc* 二、从带有ε-边的NFA到DFA的转换 r=0*1*2* 三、子集构造法( subset construction) 输入:NFA N 输出... -
DFA(确定的有穷自动机)的化简
2020-12-10 22:10:03DFA(确定的有穷自动机)的化简一、 实验目的二、 实验内容三、 实验环境四、 算法与实验原理五、 实验代码六、 实验结论七、 实验遇到的问题八、 实验心得 一、 实验目的 通过设计、编写和调试将确定的有穷自动机的... -
编译原理,确定有穷自动机DFA最小化
2016-11-11 09:19:58对于P中的一个集合I,寻找I每一个元素K,找到K从边a对应的节点,加入集合I1,若I1是P中某个集合的子集,跳至步骤3,若不是,步骤4. 3, 寻找P中下一个集合,执行步骤2,若所有集合均是子集,则步骤5. 4, 将I1... -
DFA确定性有穷自动机及其化简
2020-12-12 16:07:46确定有穷自动机就是说当一个状态面对一个输入符号的时候,它所转换到的是一个唯一确定的状态。 表示 例子 那么可以根据上面的5元组,绘制出下面的状态转移图。 解释:q0,q1,q2都是状态,所以都是节点,其中q0是... -
编译原理实验 DFA(确定的有穷自动机)的化简
2018-05-11 21:54:35令s是一个代表状态,而且假设:在DFA M中,输入为a时有从s到t转换。令t所在组的代表是r,那么在M’中有一个从s到r的转换,标记为a。令包含s0的状态组的代表是M’的开始状态,并令M’的接受状态是那些属于F的状态所在... -
确定有限自动机DFA&非确定有限自动机NFA
2020-10-27 16:12:13自动机介绍:有穷自动机(finite state automata)是一个识别器,它对每个输入的字符做识别和判断,以确定其能到达的最终状态或状态集和路径,有穷自动机分为两类,即不确定的有穷自动机NFA和确定的有穷自动机DFA[1]... -
有穷自动机
2017-12-29 13:41:19有穷自动机为一种识别装置,能准确地识别正规集。它为词法分析程序的自动构造提供了有效的方法和工具。 有穷自动机分为两类: 确定的有穷自动机 (Deterministic Finite ...一个确定的有穷自动机(DFA)M是一个五元组 -
C语言 确定有限状态自动机 DFA
2018-06-18 02:00:14确定有限状态自动机简介 实现过程 实现分析 代码实现 ...确定有限状态自动机简介 ...关于什么是DFA,可参考链接:有穷自动机DFA&NFA 本篇的主要目的是实现DFA。 实现过程 下面是一个字符串ABABAC的DF... -
Lucene 7.5.0源码 Automaton 确定型有穷自动机
2019-04-18 01:04:42这种自动机在读任何输入序列后只能处在一个状态中,术语“确定型”是指这样的事实:在每个输入上存在且仅存在一个状态,自动机可以从当前状态转移到这个状态。 在Lucene,跟DFA相关功能有 通配符查询(WildcardQuery... -
有穷自动机NFA和DFA的概念理解
2020-06-03 08:56:32有穷状态机(finite automata)分为不确定的有穷状态机(Nondeterministic Finate Automata,NFA)和确定的有穷状态机(Deterministic FiniteAutomata,DFA)。 NFA和DFA都是有限状态机,一个是不确定的,一个是确定... -
确定的有穷自动机的最小化
2013-04-17 13:00:00最后,在每个子集选出一个代表,同时消去其他等价状态。 简化算法--分割法 1.把DFA状态分割成两个状态S1’(终止状态集)和S2’(非终止状态集)。 2.对每个状态集按下述方法进行分割: 设第i次分割把集合分割成S=S1... -
确定有穷自动机(deterministic finite automata ,DFA)
2019-04-15 20:06:00是一个五元组 M=(S,∑,f,S0,F) 其中 S:有穷状态集 ∑:输入字母表(有穷) f:状态转换函数。f(S,a)=S' 是单值部分映射,每个状态面临一个输入符号时,转入的后继状态是确定的。 S0∈S:唯一初态 F∈S:终态... -
形式语言自动机(3)—— 三种有穷自动机
2019-10-17 20:58:15确定有穷自动机DFA :是一个五元组:M=(Q,∑,δ,q0,F)M = (Q,∑,δ,q_0,F)M=(Q,∑,δ,q0,F),其中 QQQ是有穷状态集; ∑∑∑是有穷的输入字母表 δδδ是转移函数,它进行全映射Q×∑→QQ×∑→QQ... -
不同正则库使用的引擎以及自动机DFA/NFA
2019-01-03 10:25:09正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机)Deterministic FiniteAutomation,另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串,一个捏在手里,一个吃下去... -
正规式转确定有穷自动机(NFA)
2017-03-19 15:57:49一,先把正规式转换为NFA(非确定有穷自动机), 二,在把NFA通过“子集构造法”转化为DFA, 三,在把DFA通过“分割法”进行最小化。 一步很简单,就是反复运用下图的规则,图1 这样就能转换到NFA了。 给... -
有穷自动机(Finite Automate)及其分类和转化
2020-08-24 11:57:14有穷自动机(Finite Automate)及其分类和转化 自我理解 有穷自动机在我目前浅薄的知识看来就是在词法分析阶段...确定的有穷自动机(Deterministic finite automate,DFA) 不确定的有穷自动机(Nondeterministic finite au -
编译原理 [0x02][0x02] ==(3.3) 词法分析__确定有限自动机和非确定有限自动机
2019-09-18 15:29:29确定有限自动机(Deterministic Finite Automata,DFA) M是一个五元式 M=(S, , f, S0, F),其中: 1.S: 有穷状态集 2.:输入字母表(有穷) 3.f : 状态转换函数,为S´SS的单值部分映射,f(s,a)=s’表示:当现行... -
有限自动机
2020-05-07 09:17:17∑: 是一个有穷字母表,它的每一个元素称为一个输入符号; f: 是转换函数,定义了从上的一个单值映射,即,指明当前的状态为p,当输入符号为a时,则转换到下一个状态q,q称为p的后继状态; S0: 是一个唯一的初始状态... -
python 两种高效过滤敏感词算法--DFA算法和AC自动机算法
2019-05-15 10:08:12一道bat面试题:快速替换10亿条标题中的5万个敏感词,有哪些解决思路? 有十亿个标题,存在一个文件中,一行一个标题。有5万个敏感词,存在另一...DFA即Deterministic Finite Automaton,也就是确定有穷自动机。 算... -
自动机的一些算法和应用
2012-08-31 19:37:48几个月前实现了一个自动相关的算法,在一个比较乐观的测试中,将一个2.3G的url集合压缩到了27M,...自动机的实现,这里说的自动机,指确定性的有穷状态自动机(DFA: Deterministic Finite Automata)。关于非确定性的有穷 -
面试:两种高效过滤敏感词算法--DFA算法和AC自动机算法
2020-03-26 23:17:27一道bat面试题:快速替换10亿条标题中的5万个敏感词,有哪些解决思路? 有十亿个标题,存在一个文件中,一行一个标题。...DFA即Deterministic Finite Automaton,也就是确定有穷自动机。 算法核心是建立了... -
软考编译原理:有限自动机
2019-05-08 20:27:42转自:... 有限自动机也称有穷自动机。 重点: NFA(不确定的有限自动机)与DFA(确定的有限自动机)的定义 NFA转化为DFA 正规式与有限自动机之间的转化 M是一个5元...