正则表达式转DFA
一、 设计原理
1. 正则表达式转换为带ε的NFA（Thompson构造法）
2. ε-NFA转为DFA
3. 最小化DFA
4. DFA状态转换表判断是否接受输入字符串
二、 算法描述
1. 正则表达式转换为NFA
（1） 建立字母表。输入的正则表达式由于一般不输入“与”操作符，因此首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。
（2） Thompson构造法。首先将构成正则表达式的各个元素分解，对于每一个元素，按照下
述规则1和规则2生成NFA。 注意：如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。
规则1 对于空记号ε，生成下面的NFA。
规则2 对于Σ的字母表中的元素a，生成下面的NFA。
所有字符生成完之后，便根据规则3，把生成的NFA组合在一起。
规则3 令正则表达式s和t的NFA分别为N(s)和N(t)。
a) 对于s|t，按照以下的方式生成NFA N(s|t)。
b) 对于st，按照以下的方式生成NFA N(st)。
c) 对于s*，按照以下的方式生成NFA N(s*)。
d) 对于(s)，使用s本身的NFA N(s)。
（3） 记录含Epsilon的NFA状态之间转换及输入字母。由于Epsilon符号不能输出，因此在程序中了利用$代替。
2. ε-NFA转为DFA
    利用ε-closure规则即闭包规则，把NFA状态划分成集合，而后把每个集合作为DFA的状态。详细描述：从NFA的状态S开始经过ε到达的状态存储下，然后再把存储结果中的状态有经过ε到达的新状态也存储在一起，这样通过闭包规则就可以这些集合，再把集合作为DFA的状态。
3. 最小化DFA
取出正则化网络DFA状态中的不可达的状态。
4. DFA状态转换表判断是否接受输入字符串
利用上次编写的DFA程序中的方法，把状态转换表放入二维数组，再通过读入输入字符串的一个字符状态跳转，假如读完输入串后的结果是到达终态，那么表明该字符串被自动机接受，否则不接受。
三、 运行结果
输入的正则表达式是：(a|b)*aabb
输入的字符串为：abbaabb,aabbaab
DOS运行结果：
输入字符串aabbaab的结果，与上面相同的正则表达式
四、 小结
    通过正则表达式到DFA这个程序的编写，自己不仅从网上相关资料借鉴编写代码，还把自己编写的DFA小程序中的代码利用，逐步加深了自己对C的学习。而且还对课堂上学习的正则表达式、NFA及DFA有了更为清楚的理解。但是自己也能够明显发觉到自身C语言的学习有很多地方还不够到位，甚至于不了解，所以只有通过不断的编程来提过自己的能力。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。