学习编译原理Time09 ~ 正则表达式转化为有穷自动机

在说从正则表达式到有穷自动机之前，想提一下不确定的有穷自动机，因为正则表达式转化为确定的有穷自动机(DFA)是比较困难，而正则表达式转化为不确定的有穷自动机(NFA)是比较好实现的，本文就记录这个，下一篇笔记再谈谈NFA转化为DFA。

首先简单说一下，不确定的有穷自动机(NFA)

M=(S ,  ∑ , δ , s0, F )

S：有穷状态集

∑：输入字母表，即输入符号集合。假设 ε 不是∑中的元素

δ：将S X ∑映射到2^S的转换函数。 s ∈S ，a∈∑，δ(s,a)表示从状态s出发，沿着标号为a的边所能到达的状态集合（与DFA唯一区别的点）

s0：开始状态(或初始状态)，s0∈S

F：接收状态(或终止状态)集合，FS

示例一个不确定的有穷自动机如下：

根据转换图可以看出，状态0遇到符号a的时候，就进入状态集合中，集合包含状态1和状态0；状态0遇到符号b的时候，就进入状态集合中，只包含状态0，同理，状态1遇到符号b的时候，就进入状态集合中，只包含状态2，...

接下来的就是根据正则表达式构造NFA

直接举一个例子：

r=(a | b)*abb

第一步：首先确定初始状态和终止状态，然后将有向边上的表达式进行分解

第二步：然后确定后缀部分abb，已经不能分解了

第三步：分解（a|b）*，因为带*是克林闭包

第四步：再分解，最终转化成NFA

    

记录

点点滴滴的笔记

欢迎关注，共同学习

小浩笔记