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

摘要

为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA.%To study the minimal deterministic finite automaton (DFA) of recognizing the strong semilattice of monoids,the R classes of the strong semilattice of monoids are investigated.That the numbers of R classes in the strong semilattice of monoids are equal to the the numbers of the monoids,and that the R class 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.