中國化工學會

[拼音]：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 ofSequentialMachines， Printice-Hall， Englewood Cliff，N.J.，1966.