半自動機

半自動機是三元組

，這裏的

是叫做“輸入字母表”的非空集合，Q是叫做“狀態集合”的非空集合，而T是“轉移函數”，

當狀態集合Q是有限集合（不是必須的!）的時候，半自動機可以被認為是確定有限自動機，但是沒有“初始狀態”

或“接受狀態”的集合A。它還可以被認為是沒有輸出只有輸入的有限狀態自動機。

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

設

是從字母表生成的自由幺半羣，（上標* 要被理解為是Kleene星號）；它是由在

中字母構成的所有有限長度字符串的集合。

對於所有

中的字w，設

是如下遞歸定義的函數，對於所有Q中的q:

如果

，則

，所以空字不改變狀態。

如果

是

中的字母，則

。

如果

對於

和

，則

。

設

是個集合

集合

在函數複合下閉合；就是説，對於所有

，有着

。它還包含

，它是S上的恆等函數。因為函數複合根據定義是結合性的，集合

是幺半羣：它叫做半自動機

的輸入幺半羣、特徵幺半羣、特徵半羣或轉移幺半羣。

變換半羣或變換幺半羣是由集合（通常稱為“狀態集合”），和映射

到自身的函數或“變換”

之幺半羣或半羣構成的有序對

。此類函數意指

中的每個元素

均為一

映射。若

和

是這個變換半羣的兩個不同函數，則半羣乘積可直覺地由函數複合得出，故吾人將

定義為

。

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

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

它滿足性質

此處1表幺半羣之單位元素，並且

，

對所有

和

，三元組

被稱為右

-act或簡稱右-act。一般而言，

表示“

的元素與

的元素的右乘法”。右-act經常寫為

。

左-act定義類似，即

並經常表示為

。

一個

-act變換半羣十分相似，然而

的元素本身不必然為函數，它們僅是某個幺半羣的元素。所以，必須限制

的作用與幺半羣中的乘法一致（亦即，

），因為一般而言，對於某個任意

此性質可能不成立，保證此一致性可使進行函數複合時不致出問題。

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

-act和變換幺半羣的另一個差異在於，對一個

，幺半羣的兩個相異元素可能決定同樣的Q變換。若我們限制其發生，則

-act與變換幺半羣便完全相同。

完全變換幺半羣（或完全變換半羣）是所有映射

的蒐集。完全變換幺半羣是自由幺半羣，在允許所有可能性的意義上。完全變換幺半羣的一個特殊情況是置換羣。

M-同態是映射

使得

對於所有

和

。所有M-同態的集合通常寫為

或

。

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

狀態集合Q不需要是有限的。作為例子，半自動機鞏固了量子有限自動機的概念。它的狀態集合Q由復投影空間給出，單獨狀態別稱為n-狀態qubit。狀態轉移給出自酉n×n矩陣。輸入字母表

仍是有限的，而其他自動機理論的典型關鍵概念仍有效。因此，量子半自動機可簡單的定義為三元組

當字母表

有p個字母的時候，所以對每個字母

都有一個酉矩陣

。這種方式規定之後，量子半自動機明顯有多種幾何推廣。比如，可以用黎曼對稱空間替代

，並從它的等距羣選出轉移函數。

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

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