半自动机

变换半群或变换幺半群是由集合${\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))}$ 。

注意“半群”与“幺半群”的使用：有些作者将“半群”与“幺半群”视为同义词。然而此处一个半群不必然包含单位元素；而一个幺半群则意指含有单位元素的半群。因为作用于集合上的函数概念永远包括恒等函数概念在内，亦即施加于集合上时不做任何动作，故变换半群可借由与恒等函数联集转为幺半群。

设${\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-同态是映射

${\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。对象是M-act，而范畴的态射是M-同态。

• John M. Howie, Fundamentals of Semigroup Theory（1995）, Clarendon Press, Oxford Nico F. Benschop, Associative Digital Network Theory（页面存档备份，存于互联网档案馆） An Associative Algebra Approach to Logic, Arithmetic and State Machines（2003）Amspade Research, Geldrop, The Netherlands.