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

摘要

为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA.