识别幺半群强半格的最少状态DFA  

The minimal deterministic finite automaton recognizing the strong semilattice of finite monoids

作　　者：黎宏伟[1] 

机构地区：[1]宿迁学院文理学院,江苏宿迁223800

出　　处：《江苏师范大学学报（自然科学版）》2017年第4期36-38,共3页Journal of Jiangsu Normal University：Natural Science Edition

基　　金：江苏省高校自然科学基金资助项目(10KJB58005)

摘　　要：为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA.To study the minimal deterministic finite automaton(DFA)of recognizing the strong semilattice of monoids,the Rclasses of the strong semilattice of monoids are investigated.That the numbers of Rclasses in the strong semilattice of monoids are equal to the the numbers of the monoids,and that the Rclass of a semigroup is a right invariant equivalence class of the regular language are found.Relying on these two conclusions,that the numbers of the terminal states in the minimal DFA are equal to the numbers of the monoids is proved,and the minimal DFA is constructed.

关 键 词：强半格 幺半群 确定型有穷自动机 

分 类 号：O152.7[理学—数学] O158[理学—基础数学]