| 有限自动机最小化算法的实现 |
| |
| 引用本文： | 韩光辉.有限自动机最小化算法的实现[J].武汉市经济管理干部学院学报,2006,20(1):60-62. |
| |
| 作者姓名： | 韩光辉 |
| |
| 作者单位： | 武汉商业服务学院,湖北武汉430056 |
| |
| 摘 要： | 实现DFAM=（Q，∑，σ，qo,F）最小化算法的关键问题是如何编程求取商集Q／Rk（即状态的k阶区分）。本文引入等价关系Sk与商集Q／Sk（状态的严格k阶区分），证明了Rk=Rk-1∩Sk，因此Q／Rk是Q／Rk-1中等价类与Q／Sk中等价类的非空交集全体。为了求取Q／Sk，引入Q的子集Hk，利用集合的交、差运算可由Hk求取Q／Sk，从而仅利用集合运算便可求取Q／Rko基于上述讨论，给出了DFA最小化算法的一个容易实现的构造性描述。
|
| 关 键 词： | 有限自动机 等价最小有限自动机 等价关系 商集 划分 |
| 文章编号： | 1009-2277（2006）01-0060-03 |
| 收稿时间： | 2005-12-20 |
| 修稿时间： | 2005-12-20 |
An Implementation of the Minimization Algorithm of DFA |
| |
| HAN Guang-hui.An Implementation of the Minimization Algorithm of DFA[J].Journal of Wuhan Economic Administration Cadre's College,2006,20(1):60-62. |
| |
| Authors: | HAN Guang-hui |
| |
| Institution: | HAN Guang-hui |
| |
| Abstract: | |
| |
| Keywords: | deterministic finite automata minimum equivalent finite automaton equivalence relation quotient set partition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
