半自动机

在数学和计算机科学中，半自动机或${\displaystyle M}$-集合、-集合、-操作数、-系统、-自动机、转移系统、算子幺半群、变换半群或转移幺半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。

变换半群或变换幺半群是由集合${\displaystyle Q}$是叫做“状态集合”的非空集合，而是“转移函数”，

当状态集合是有限集合（不是必须的!）的时候，半自动机可以被认为是确定有限自动机${\displaystyle (Q,\mathrm{\Sigma <!--\; \Sigma \; -->},T,q_0,A)}$。它还可以被认为是没有输出只有输入的有限状态自动机。

幺半群理论的一个主要主张是半自动机等价于act；所以对于任何act，都有一个唯一的半自动机，或反过来说，对于任何半自动机，都有一个唯一的act。这可以如下这样证实。

设${\displaystyle {\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}}$，设${\displaystyle T_w:Q\to <!--\; \to \; -->Q}$中的:

设${\displaystyle M(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},T)}$上的恒等函数。因为函数复合根据定义是结合性的，集合${\displaystyle M(Q,\mathrm{\Sigma <!--\; \Sigma \; -->},T)}$-同态是映射

使得

对于所有${\displaystyle q\in <!--\; \in \; -->Q}$-同态的集合通常写为${\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(Q_M,B_M)}$是有限的，则转移函数通常表示为状态转移表。在自由群中字符串所驱动的所有可能转移的构造有一种叫de Bruijn图的图形描述。

状态集合不需要是有限的。作为例子，半自动机巩固了量子有限自动机的概念。它的状态集合由复投影空间${\displaystyle \mathbb{C}{P}^n}$-状态qubit。状态转移给出自酉×矩阵。输入字母表${\displaystyle \mathrm{\Sigma <!--\; \Sigma \; -->}}$个字母的时候，所以对每个字母${\displaystyle \mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->\mathrm{\Sigma <!--\; \Sigma \; -->}}$-act，而范畴的态射是-同态。