自動機的半群理論

使用半群理論研究自動機的結構及自動機的分解問題。(，，，，)是一有限自動機（見有限自動機論）,是中元素組成的字元序列集合。對有限自動機輸入中的一個字元序列後，的每一個狀態都要分別變到另外一個狀態，因此，引導出狀態集合上的一個變換,簡記為【】。的所有由中字元序列引導出的變換，構成一個半群，這個半群稱為有限自動機的半群。

正文

使用半群理論研究自動機的結構及自動機的分解問題。(，，，，)是一有限自動機（見有限自動機論）,是中元素組成的字元序列集合。對有限自動機輸入中的一個字元序列後，的每一個狀態都要分別變到另外一個狀態，因此，引導出狀態集合上的一個變換,簡記為【】。的所有由中字元序列引導出的變換，構成一個半群，這個半群稱為有限自動機的半群。
若是一個有限含壹半群,則可用構造一個有限自動機()=(，，,，)，即此有限自動機的輸入集合、輸出集合和狀態集合都是,而函式和的定義為

δ(s，s′)=s*s′ 　λ(s，s′)=s

這裡s和s′是半群的元素,*是半群中的乘法。這個有限自動機稱為半群的自動機。若是一個單群，可把單群的自動機叫單群自動機。
在建立大型系統時，人們往往考慮把較小的基本系統當作部件構造較大系統的問題。這個問題反過來看就是給定一個系統的功能描述，是否可以把它分解成一些較小系統的問題。這就是有限自動機的分解問題,它主要研究什麼樣的有限自動機能夠分解，一些不可分解的基本有限自動機是什麼樣的，如何分解一個有限自動機等。
自動機的聯結有兩種基本方式，一種是串聯，另一種是並聯。因而分解也就有串列分解和並行分解兩種形式。為進一步研究分解問題，人們把這兩種聯結形式統一在一起，形成級聯的概念，然後研究有限自動機的級聯分解問題。有限自動機的級聯分解問題與有限自動機的半群的結構緊密聯繫在一起。當有限自動機的半群是一個群時，其級聯分解問題類似於求群的正規子群和商群的問題。根據半群的結構理論與群的整除性理論，K.克勞恩和J.L.羅茲於1965年證明了下述重要定理：若為一有限自動機，是的半群,則可級聯分解為一些簡單的有限自動機,這些簡單的自動機或者是觸發器,或者是單群自動機，其單群整除。