半自動機

在數學和計算機科學中，半自動機或${\displaystyle M}$-act是么半群在集合上的乘法性運算。從代數結構的觀點來看，它非常接近於群作用的概念。從計算機科學的觀點來看，它是只有輸入沒有輸出的自動機。從範疇論的觀點來看，作用是如範疇上的函子般重要。

這個概念也叫做S-集合、M-集合、M-操作數、S-系統、S-自動機、轉移系統、算子么半群、變換半群或轉移么半群。本文力圖表現出它們表示的是同一個概念，儘管在使用中有各種概念和術語的變體。

變換半群

變換半群或變換么半群是由集合${\displaystyle Q}$（通常稱為「狀態集合」），和映射${\displaystyle Q}$到自身的函數或「變換」${\displaystyle M}$之么半群或半群構成的有序對${\displaystyle (M,Q)}$。此類函數意指${\displaystyle M}$中的每個元素${\displaystyle m}$均為一${\displaystyle m:Q\to Q}$映射。若${\displaystyle s}$和${\displaystyle t}$是這個變換半群的兩個不同函數，則半群乘積可直覺地由函數複合得出，故吾人將${\displaystyle (st)(q)}$定義為${\displaystyle (s\circ t)(q)=s(t(q))}$。

注意「半群」與「么半群」的使用：有些作者將「半群」與「么半群」視為同義詞。然而此處一個半群不必然包含單位元素；而一個么半群則意指含有單位元素的半群。因為作用於集合上的函數概念永遠包括恆等函數概念在內，亦即施加於集合上時不做任何動作，故變換半群可藉由與恆等函數聯集轉為么半群。

M {\displaystyle M} -acts

設${\displaystyle M}$是么半群而${\displaystyle Q}$是非空集合。如果存在一個乘法運算

${\displaystyle \mu :Q\times M\to Q}$ ${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

它滿足性質

${\displaystyle q1=q}$，

此處1表么半群之單位元素，並且

${\displaystyle q(st)=(qs)t}$，

對所有${\displaystyle q\in Q}$和${\displaystyle s,t\in M}$，三元組${\displaystyle (Q,M,\mu )}$被稱為右${\displaystyle M}$-act或簡稱右-act。一般而言，${\displaystyle \mu }$表示「${\displaystyle Q}$的元素與${\displaystyle M}$的元素的右乘法」。右-act經常寫為${\displaystyle Q_{M}}$。

左-act定義類似，即

${\displaystyle \mu :M\times Q\to Q}$ ${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

並經常表示為${\displaystyle \,_{M}Q}$。

一個${\displaystyle M}$-act變換半群十分相似，然而${\displaystyle M}$的元素本身不必然為函數，它們僅是某個么半群的元素。所以，必須限制${\displaystyle \mu }$的作用與么半群中的乘法一致（亦即，${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$），因為一般而言，對於某個任意${\displaystyle \mu }$此性質可能不成立，保證此一致性可使進行函數複合時不致出問題。

一旦加上這種限制，就可以完全放心的去掉所有括號，因為么半群乘積和么半群在集合上的作用是完全滿足結合性的。特別是這允許了么半群的元素被表示為計算機科學意義上字母的字符串。這種抽象接着允許談論一般的字符串運算，並最終導致了由字母的字符串構成的形式語言概念。

${\displaystyle M}$-act和變換么半群的另一個差異在於，對一個${\displaystyle M}$-act ${\displaystyle Q}$，么半群的兩個相異元素可能決定同樣的Q變換。若我們限制其發生，則${\displaystyle M}$-act與變換么半群便完全相同。

完全變換么半群

完全變換么半群（或完全變換半群）是所有映射${\displaystyle m:Q\to Q}$的搜集。完全變換么半群是自由么半群，在允許所有可能性的意義上。完全變換么半群的一個特殊情況是置換群。

半自動機

半自動機是三元組${\displaystyle (Q,\Sigma ,T)}$，這裏的${\displaystyle \Sigma }$是叫做「輸入字母表」的非空集合，Q是叫做「狀態集合」的非空集合，而T是「轉移函數」，

${\displaystyle T:Q\times \Sigma \to Q}$

當狀態集合Q是有限集合（不是必須的!）的時候，半自動機可以被認為是確定有限自動機${\displaystyle (Q,\Sigma ,T,q_{0},A)}$，但是沒有「初始狀態」 ${\displaystyle q_{0}}$或「接受狀態」的集合A。它還可以被認為是沒有輸出只有輸入的有限狀態自動機。

么半群理論的一個主要主張是半自動機等價於act；所以對於任何act，都有一個唯一的半自動機，或反過來說，對於任何半自動機，都有一個唯一的act。這可以如下這樣證實。

設${\displaystyle \Sigma ^{*}}$是從字母表${\displaystyle \Sigma }$生成的自由么半群，（上標* 要被理解為是Kleene星號）；它是由在${\displaystyle \Sigma }$中字母構成的所有有限長度字符串的集合。

對於所有${\displaystyle \Sigma ^{*}}$中的字w，設${\displaystyle T_{w}:Q\to Q}$是如下遞歸定義的函數，對於所有Q中的q:

• 如果${\displaystyle w=\varepsilon }$，則${\displaystyle T_{\varepsilon }(q)=q}$，所以空字${\displaystyle \varepsilon }$不改變狀態。

• 如果${\displaystyle w=\sigma }$是${\displaystyle \Sigma }$中的字母，則${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$。

• 如果${\displaystyle w=\sigma v}$對於${\displaystyle \sigma \in \Sigma }$和${\displaystyle v\in \Sigma ^{*}}$，則${\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}$。

設${\displaystyle M(Q,\Sigma ,T)}$是個集合

${\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}}$

集合${\displaystyle M(Q,\Sigma ,T)}$在函數複合下閉合；就是說，對於所有${\displaystyle v,w\in \Sigma ^{*}}$，有着${\displaystyle T_{w}\circ T_{v}=T_{vw}}$。它還包含${\displaystyle T_{\varepsilon }}$，它是S上的恆等函數。因為函數複合根據定義是結合性的，集合${\displaystyle M(Q,\Sigma ,T)}$是么半群：它叫做半自動機${\displaystyle (Q,\Sigma ,T)}$的輸入么半群、特徵么半群、特徵半群或轉移么半群。

M-同態

M-同態是映射

${\displaystyle f:Q_{M}\to B_{M}}$

使得

${\displaystyle f(qm)=f(q)m}$

對於所有${\displaystyle q\in Q}$和${\displaystyle m\in M}$。所有M-同態的集合通常寫為${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$或${\displaystyle \mathrm {Hom} _{M}(Q,B)}$。

性質

如果狀態集合Q是有限的，則轉移函數通常表示為狀態轉移表。在自由群中字符串所驅動的所有可能轉移的構造有一種叫de Bruijn圖的圖形描述。

狀態集合Q不需要是有限的。作為例子，半自動機鞏固了量子有限自動機的概念。它的狀態集合Q由復投影空間${\displaystyle \mathbb {C} P^{n}}$給出，單獨狀態別稱為n-狀態qubit。狀態轉移給出自酉n×n矩陣。輸入字母表${\displaystyle \Sigma }$仍是有限的，而其他自動機理論的典型關鍵概念仍有效。因此，量子半自動機可簡單的定義為三元組${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\cdots ,U_{\sigma _{p}},\})}$當字母表${\displaystyle \Sigma }$有p個字母的時候，所以對每個字母${\displaystyle \sigma \in \Sigma }$都有一個酉矩陣${\displaystyle U_{\sigma }}$。這種方式規定之後，量子半自動機明顯有多種幾何推廣。比如，可以用黎曼對稱空間替代${\displaystyle \mathbb {C} P^{n}}$，並從它的等距群選出轉移函數。

形式語言的語法么半群同構於到接受這個語言的極小自動機的轉移么半群。

範疇Act

定義右作用的代數關係形成了一個範疇Act。對象是M-act，而範疇的態射是M-同態。

引用

• John M. Howie, Fundamentals of Semigroup Theory（1995）, Clarendon Press, Oxford ISBN 0-19-851194-9
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories（2000）, Walter de Gruyter, Berlin ISBN 3-11-015248-7
• A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups. American Mathematical Society,（1961）volume 1,（1967）volume 2.
• F. Gecseg and I. Peak, Algebraic Theory of Automata（1972）, Akademiai Kiado, Budapest.
• Nico F. Benschop, Associative Digital Network Theory（頁面存檔備份，存於互聯網檔案館） An Associative Algebra Approach to Logic, Arithmetic and State Machines（2003）Amspade Research, Geldrop, The Netherlands.