[拼音]：zidongji de banqun lilun
[外文]：automata semigroup theory
使用半群理论研究自动机的结构及自动机的分解问题。M(X，Y，Q，δ，δ)是一有限自动机（见有限自动机论），X*是X中元素组成的字符序列集合。对有限自动机M输入X*中的一个字符序列后，Q的每一个状态都要分别变到另外一个状态，因此，x引导出状态集合Q上的一个变换，简记为[x]。Q的所有由X*中字符序列引导出的变换，构成一个半群，这个半群称为有限自动机M的半群。
若S是一个有限含壹半群，则可用S构造一个有限自动机M(S)＝(S，S，S，δ，λ)，即此有限自动机的输入集合、输出集合和状态集合都是S，而函数δ和λ的定义为
δ(s，s′)＝s*s′
λ(s，s′)＝s
这里s和s′是半群S 的元素，*是半群中的乘法。这个有限自动机称为半群S的自动机。若S是一个单群，可把单群S的自动机叫单群自动机。
在建立大型系统时，人们往往考虑把较小的基本系统当作部件构造较大系统的问题。这个问题反过来看就是给定一个系统的功能描述，是否可以把它分解成一些较小系统的问题。这就是有限自动机的分解问题，它主要研究什么样的有限自动机能够分解，一些不可分解的基本有限自动机是什么样的，如何分解一个有限自动机等。
自动机的联结有两种基本方式，一种是串联，另一种是并联。因而分解也就有串行分解和并行分解两种形式。为进一步研究分解问题，人们把这两种联结形式统一在一起，形成级联的概念，然后研究有限自动机的级联分解问题。有限自动机的级联分解问题与有限自动机的半群的结构紧密联系在一起。当有限自动机的半群是一个群时，其级联分解问题类似于求群的正规子群和商群的问题。根据半群的结构理论与群的整除性理论，K.克劳恩和J.L.罗兹于1965年证明了下述重要定理：若M为一有限自动机，S是M的半群，则M可级联分解为一些简单的有限自动机，这些简单的自动机或者是触发器，或者是单群自动机，其单群整除S。
- 参考书目
- M.A.Arbib， Theories of Abstract Automata， Printice-Hall，Englewood Cliff， N.J.，1969.
- J.Hartmanis， R.E.Stearns， Algebraic Structure Theory of Sequential Machines， Printice-Hall， Englewood Cliff，N.J.，1966.
