自动机
自动机,顾名思义,就是能够自动完成事情的“机器”。但是为什么要用自动机,什么又叫“自动”呢?
我们看看普通的处理方式,简单的就是if了,例如:判断某字符串是否是“Hello,Word”,我们都会这么写:
if(str == “Hello,Word”)
普通的比较可以满足大部分的场景,但对于正则表达式这种比较的话,普通的if就完全不能满足了,例如a*b|c,可以是如下字符串:
ab
aab
aaaab
c
………….
这种情况我们不可能采用普通的if来判断了,因为不可能穷举所有的字符串。所以我们要另辟蹊径,自动机就应运而生了。
我们这里讲的自动机有两个:一个是确定有限自动机,又叫DFA;一个叫不确定有限自动机,又叫NFA。由于自动机的核心就是通过“状态”和“状态变迁”实现的,所以自动机又叫状态机。
1) NFA
为什么叫不确定自动机呢?就是因为存在“不确定性”了。
什么不确定呢?就是一个输入可能对应多个状态转换,所以就不确定了。
通过NFA来识别字符串的过程很简单,即每输入一个字符,都判断当前的状态集中哪些状态上有此字符的转换,然后把所有转换后的状态又记录下来,依此循环,直到字符输入结束或者状态机结束。
不知道大家有没有发现,NFA的识别过程其实非常类似将NFA转换到DFA的子集构造算法的过程。如下图:
NFA识别过程,假如识别aabb
(1)初始状态:0,1,2,4,7
(2)输入a,转换到如右的状态:3, 6, 7, 1 , 2 ,4,
(3)输入a,转换到如右的状态:8, 3, 6 , 7, 1, 2, 4
(4)输入b,转换到如右的状态:9, 5, 6, 7, 1, 2, 4
(5)输入b,转换到如右的状态:10, 5, 6, 7, 1, 2, 4
由于此时已经没有输入字符了,而且最终状态10也包含进来了,因此aabb就接受了。
NFA->DFA的子集构造算法:
(1)初始状态:0,1,2,4,7(第一个子集)
(2)输入a,转换到如右的状态:3, 6, 7, 1 , 2 ,4(第二个子集)
(3)输入a,转换到如右的状态:8, 3, 6 , 7, 1, 2, 4(第三个子集)
………………………..(依次类推)…………………………………………..
2) DFA.
介绍到这里,相信大家都已经明白DFA的概念了。
所谓确定,就是指一个输入只能对应一个转换。
而DFA来识别字符串就更简单了,由于转换是确定的,所以直接将输入字符输入进行转换即可。
3) NFA和DFA比较.
复杂度:当然是DFA高了;
速度:当然是DFA快了
到这里正则表达式系列相关知识也就结束了,当然我在这里知识提纲挈领,让大家能够从整体上把握这些相关的东东,不至于上来就被一堆术语和名词弄晕了,同时也把关键的地方点了一下,希望能够起到让大家茅塞顿开的效果。
当然更加详细和深入的研究还需要各位自己深入钻研了,推荐《编译原理(龙书)》和《精通正则表达式》两本书。
分享到:
相关推荐
这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦. 一个正则表达式就是由普通字符(例如字符 a 到 z)以及特殊字符(称为元字符)组成的文字模式...
正则表达式与自动机的转换,以及自动机的化简
1、资源内容:Matlab字符操作进阶:正则表达式(源码).rar 2、代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 3、适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业...
从正则表达式到有穷自动机实例 从正则表达式到有穷自动机实例
正则表达式规则及常用正则表达式列举,应该很全了
由正则表达式生成有限自动机,显示有限自动机的状态和动作等,方便学习有限自动机课程。
课程设计 正规式构造nfa.这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦。
一个VC++正则表达式 有穷自动机实例源码,请输入正则式( 注意对单个输入有*操作的时候要有$合成,比如求0*,要有($0)* ): 。编译后程序会生成一个可执行文件,运行这个文件出来一个DOS窗口,然后按提示输入正则...
想研究透彻正则表达式,必须知道有穷自动机的原理,这个源码可以给你一个很好的示例参考。编译后程序会生成一个可执行文件,运行这个文件出来一个DOS窗口,然后按提示输入正则表达式。
介绍了构造等价于给定正则表达式的简化确定有限自动机(DFA) 的算 法. 方法是首先构造与正则表达式等价的非确定有限自动机(NFA) , 这里省略了构 造带E动作的有限自动机的操作, 然后用状态树构造与该NFA 等价的简化DFA...
代码相对简单; c语言实现; 正则表达式转换为nfa;
正则表达式和有穷自动机*(课件)!!!!!!!!!!!
使用确定性有限自动机的低级正则表达式库
经过对正则表达式合并DFA(确定型有限自动机)状态爆炸问题的分析,采用正则表达式两两合并DFA的状态增加数之和衡量多个正则表达式合并后真实的状态增加情况,将正则表达式最优分组问题归约为带权无向图的k-最大割...
基于NFA(不确定有穷自动机)与自底向上语法分析构造的正则表达式解析器
- **计算机科学或相关领域的学生**:此项目能够帮助他们实践编译原理和理论计算机科学的知识。 - **软件开发者**:特别是那些对编译器设计和自动化工具感兴趣的程序员。 - **研究者**:在编译技术、程序分析或语言...
编译原理及实现技术:5.词法分析__自动机与正则表达式、词法分析器的设计.ppt
设VT={a,b},试构造下述正则表达式的确定性有限状态自动机: (1) a(a|b)﹡baa (2) (a|b)﹡bbb﹡
一个使用Thompson构造将正则表达式转换为非确定性有限自动机(NFA)的c ++程序。 此外,它被简化为确定性有限自动机(DFA),并且有一个函数可用于检查属于给定正则表达式的各种字符串。 做得更好:) PS:-不久将...
基于正则表达式的英文单词检索系统,要求给定任意的正则表达式作为输入,将其转换为等价的自动机,并可以根据该自动机实现从输入文本中检测并输出所有符合正则表达式描述的单词。(C++实现)