正则表达式转DFA.doc

《正则表达式转DFA.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、正则表达式转DFA一、设计原理1.正则表达式转换为带ε的NFA（Thompson构造法）2.ε-NFA转为DFA3.最小化DFA4.DFA状态转换表判断是否接受输入字符串二、算法描述1.正则表达式转换为NFA（1）建立字母表。输入的正则表达式由于一般不输入“与”操作符，因此首先给表达式加入.作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。（2）Thompson构造法。首先将构成正则表达式的各个元素分解，对于每一个元素，按照下述规则1和规则2生成NFA。注意：如果r中记号a出现了多次，那么对于a的每次出现都需要生

2、成一个单独的NFA。规则1对于空记号ε，生成下面的NFA。规则2对于Σ的字母表中的元素a，生成下面的NFA。所有字符生成完之后，便根据规则3，把生成的NFA组合在一起。规则3令正则表达式s和t的NFA分别为N(s)和N(t)。a)对于s

3、t，按照以下的方式生成NFAN(s

4、t)。b)对于st，按照以下的方式生成NFAN(st)。c)对于s*，按照以下的方式生成NFAN(s*)。d)对于(s)，使用s本身的NFAN(s)。（1）记录含Epsilon的NFA状态之间转换及输入字母。由于Epsilon符号不能输出，因此在程序中了利用$代替。2

5、.ε-NFA转为DFA利用ε-closure规则即闭包规则，把NFA状态划分成集合，而后把每个集合作为DFA的状态。详细描述：从NFA的状态S开始经过ε到达的状态存储下，然后再把存储结果中的状态有经过ε到达的新状态也存储在一起，这样通过闭包规则就可以这些集合，再把集合作为DFA的状态。3.最小化DFA取出DFA状态中的不可达的状态。4.DFA状态转换表判断是否接受输入字符串利用上次编写的DFA程序中的方法，把状态转换表放入二维数组，再通过读入输入字符串的一个字符状态跳转，假如读完输入串后的结果是到达终态，那么表明该字符串被自动机接受，否

6、则不接受。一、运行结果输入的正则表达式是：(a

7、b)*aabb输入的字符串为：abbaabb,aabbaabDOS运行结果：输入字符串aabbaab的结果，与上面相同的正则表达式一、小结通过正则表达式到DFA这个程序的编写，自己不仅从网上找相关资料借鉴编写代码，还把自己编写的DFA小程序中的代码利用，逐步加深了自己对C的学习。而且还对课堂上学习的正则表达式、NFA及DFA有了更为清楚的理解。但是自己也能够明显发觉到自身C语言的学习有很多地方还不够到位，甚至于不了解，所以只有通过不断的编程来提过自己的能力。