| 基于前序关系的非确定型有穷自动机极小化算法 |
| |
| 引用本文： | 张明明,秦永彬.基于前序关系的非确定型有穷自动机极小化算法[J].山东大学学报(理学版),2010,45(7):34-38. |
| |
| 作者姓名： | 张明明 秦永彬 |
| |
| 作者单位： | 贵州大学计算机科学与信息学院,贵州,贵阳,550025 |
| |
| 基金项目： | 贵州省自然科学基金资助项目，贵州省省长基金资助项目，贵州大学自然科学青年基金资助项目，贵州大学研究生创新基金资助项目 |
| |
| 摘 要： | 为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。
|
| 关 键 词： | 非确定型有穷自动机 前序关系 状态合并 极小化 |
| 收稿时间： | 2010-04-02 |
A non-deterministic finite automata minimization method based on preorder relation |
| |
| ZHANG Ming-ming,QIN Yong-bin.A non-deterministic finite automata minimization method based on preorder relation[J].Journal of Shandong University,2010,45(7):34-38. |
| |
| Authors: | ZHANG Ming-ming QIN Yong-bin |
| |
| Institution: | College of Computer Science and Information, Guizhou University, Guiyang 550025, Guizhou, China |
| |
| Abstract: | In order to reduce the number of non-deterministic finite automata (NFA) states, the preorder relation was introduced. The transition diagram for the NFA was regarded as a directed graph with signs based on graph theory,and then a new method of NFA minimization was proposed. Compared with the current NFA minimization algorithm based on merging the equivalent states, this method could further reduced the number of NFA states while accepting the same languages. |
| |
| Keywords: | non-deterministic finite automata preorder relation state merging minimization |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《山东大学学报(理学版)》下载免费的PDF全文 |
