半自动机

在数学和计算机科学中，半自动机或 $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)$

并经常表示为 $\,_MQ$。

一個 $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.