摘要
给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFAM=(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最小化算法的一个容易实现的构造型描述和相应示例。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第32期52-54,共3页
Computer Engineering and Applications
基金
国家自然科学基金(No.10671030)~~
关键词
格半群
确定型有限状态自动机
等价关系
商集
最小化
最小化算法
lattice-ordered monoid； deterministic lattice finite automata； equivalence relation； quotient set； minimization； minimization algorithm；
