| 构造正则表达式的简化DFA算法 |
| |
| 引用本文： | 檀凤琴.构造正则表达式的简化DFA算法[J].北京航空航天大学学报,1998,24(4):495-498. |
| |
| 作者姓名： | 檀凤琴 |
| |
| 作者单位： | 北京航空航天大学 计算机科学与工程系 |
| |
| 摘 要： | 介绍了构造等价于给定正则表达式的简化确定有限自动机(DFA)的算法.方法是首先构造与正则表达式等价的非确定有限自动机(NFA), 这里省略了构造带ε动作的有限自动机的操作, 然后用状态树构造与该NFA等价的简化DFA.这个算法在计算机上已实现, 并且对输入的任意正则表达式, 都可以输出等价于正则表达式的简化DFA.该算法可以用于某些离散信息处理系统的设计与分析.
|
| 关 键 词： | 有限自动机 状态 状态函数 识别 状态图 |
| 收稿时间： | 1998-05-11 |
Algorithm for Constructing the Simplified DFA of Regular Expressions |
| |
| Tan Fengqin.Algorithm for Constructing the Simplified DFA of Regular Expressions[J].Journal of Beijing University of Aeronautics and Astronautics,1998,24(4):495-498. |
| |
| Authors: | Tan Fengqin |
| |
| Institution: | Beijing University of Aeronautics and Astronautics,Dept. of Computer Science and Engineering |
| |
| Abstract: | An algorithm for constructing the simplified DFA(Deterministic Finite Automaton) is introduced,which is equivalent to a given regular expression. The first step constructs an NFA(Nondeterministic Finite Automaton) equivalent to the regular expression, where the operation for constructing finite automata with ε-moves is omitted. Then the simplified DFA equivalent to the NFA is constructed by using state transition trees. The algorithm bas been realized by computer programming, and for any input regular expression, a simplified DFA equivalent to the regular expression is produced. The algorithm can be applied in the design and analysis of the system with discrete inputs and outputs. |
| |
| Keywords: | finite automata states state functions recognition state diagrams |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京航空航天大学学报》浏览原始摘要信息 |
| 点击此处可从《北京航空航天大学学报》下载免费的PDF全文 |
