半自动机

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

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

## 變換半群

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

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

##  $M$ -acts

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

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

它滿足性質

 $q1=q$ ，

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

 $q(st)=(qs)t$ ， 

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

**左 - act** 定義類似，即

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

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

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

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

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

## 完全變換么半群

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

## 半自動機

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

　
: $T:Q\times \Sigma \to Q$

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

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

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

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

* 如果 $w=\varepsilon $ ，則 $T_{\varepsilon }(q)=q$ ，所以空字 $\varepsilon $ 不改變狀態。
* 如果 $w=\sigma $ 是 $\Sigma $ 中的字母，則 $T_{\sigma }(q)=T(q,\sigma )$ 。
* 如果 $w=\sigma v$ 對於 $\sigma \in \Sigma $ 和 $v\in \Sigma ^{*}$ ，則 $T_{w}(q)=T_{v}(T_{\sigma }(q))$ 。

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

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

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

## M - 同態

**_M_- 同態**是映射

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

使得

　
: $f(qm)=f(q)m$

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

## 性質

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

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