半自动机

在数学和计算机科学中，半自动机或 M-act 是幺半群在集合上的乘法性运算。从代数结构的观点来看，它非常接近于群作用的概念。从计算机科学的观点来看，它是只有输入没有输出的自动机。从范畴论的观点来看，作用是如范畴上的函子般重要。

这个概念也叫做 S-集合, M-集合, M-操作数, S-系统, S-自动机, 转移系统, 算子幺半群, 变换半群或转移么半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。

变换半群

变换半群或变换幺半群是有序对 $(M,Q)$，它构成自 集合 Q(经常叫做“状态集合”)，和映射 Q 到自身的函数或“变换”的幺半群或半群 M。它们是在 M 的所有元素 m 都是一个映射 $m:Q\to Q$ 意义上的函数。如果 s 和 t 是这个变换半群的两个不同元素，则半群乘积平凡的从函数复合的得出，所以定义 $(st)(q) \,$ 为 $(s\circ t)(q)=s(t(q))$。变换半群同下面使用稍微抽象语言定义的 M-act 完全是同一个东西。

注意“半群”与“幺半群”的使用: 尽管一些作者定义这二者是同一个东西，很多其他人做出了区分: 幺半群是带有单位元素的半群；半群是没有单位元素的幺半群。因为作用于集合上的函数的概念总是包含恒等函数的概念，变换半群在技术上应当叫做变换幺半群。此后就使用术语“幺半群”。

M-act

设 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: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.