| 确定型格值有限自动机的最小化 |
| |
| 引用本文： | 李斌,舒兰. 确定型格值有限自动机的最小化[J]. 计算机工程与应用, 2010, 46(32): 52-54. DOI: 10.3778/j.issn.1002-8331.2010.32.014 |
| |
| 作者姓名： | 李斌 舒兰 |
| |
| 作者单位： | 电子科技大学 应用数学学院，成都 610054 |
| |
| 摘 要： | 给出了确定型格值有限自动机的定义，并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFA M=Q,Σ,δ,q0,σ的实质是求取Q/Rk。由此以可到达状态为基础引入了等价关系Rk、Sk与商集Q/Sk，证明了Rk=Rk-1∩Sk，由此得到Q/Rk的等价类为Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体。引入了Hk，并证明了可由Hk求取Q/Sk，从而得到仅利用集合运算便可求取Q/Rk的算法，最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。
|
| 关 键 词： | 格半群 确定型有限状态自动机 等价关系 商集 最小化 最小化算法 |
| 收稿时间： | 2009-04-14 |
| 修稿时间： | 2009-6-22 |
Minimization of deterministic lattice finite automata |
| |
| LI Bin,SHU Lan. Minimization of deterministic lattice finite automata[J]. Computer Engineering and Applications, 2010, 46(32): 52-54. DOI: 10.3778/j.issn.1002-8331.2010.32.014 |
| |
| Authors: | LI Bin SHU Lan |
| |
| Affiliation: | College of Applied Mathematics，University of Electronic Science and Technology of China，Chengdu 610054，China |
| |
| Abstract: | The notion of deterministic lattice finite automata is proposed,and the definitions of effectual final states and reachable states are shown.Indicating that the key problem of implementing the minimization algorithm of DLFA is how to solve quotient set Q/Rk.At the base of effectual final states,the equivalence relations Rk,Sk and the quotient set Q/Sk are introduced,and Rk=Rk-1∩Sk is proved.The elements of Q/Rk are all nonempty intersections with each equivalence class belonging to Q/Rk-1 and each one belonging to Q/Sk.Hk is introduced,and it can solve Q/Sk,and therefore Q/Rk is solved using only set operations.A constructive minimization algorithm of DLFA easy to be implemented is presented based on the above discussion. |
| |
| Keywords: | lattice-ordered monoid； deterministic lattice finite automata； equivalence relation； quotient set； minimization； minimization algorithm； |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
