确定型格值有限自动机的最小化  

Minimization of deterministic lattice finite automata

作　　者：李斌[1] 舒兰[1] 

机构地区：[1]电子科技大学应用数学学院,成都610054

出　　处：《计算机工程与应用》2010年第32期52-54,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10671030)~~

摘　　要：给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取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.

关 键 词：格半群 确定型有限状态自动机 等价关系 商集 最小化 最小化算法 

分 类 号：O235[理学—运筹学与控制论] TP23[理学—数学]