半自动机

在数学和计算机科学中，半自动机或-act是幺半群在集合上的乘法性运算。从代数结构的观点来看，它非常接近于群作用的概念。从计算机科学的观点来看，它是只有输入没有输出的自动机。从范畴论的观点来看，作用是如范畴上的函子般重要。
这个概念也叫做S-集合、M-集合、M-操作数、S-系统、S-自动机、转移系统、算子幺半群、变换半群或转移幺半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。

变换半群

变换半群或变换幺半群是由集合（通常称为“状态集合”），和映射到自身的函数或“变换”之幺半群或半群构成的有序对。此类函数意指中的每个元素均为一映射。若和是这个变换半群的两个不同函数，则半群乘积可直觉地由函数复合得出，故吾人将定义为。
注意“半群”与“幺半群”的使用：有些作者将“半群”与“幺半群”视为同义词。然而此处一个半群不必然包含单位元素；而一个幺半群则意指含有单位元素的半群。因为作用于集合上的函数概念永远包括恒等函数概念在内，亦即施加于集合上时不做任何动作，故变换半群可借由与恒等函数联集转为幺半群。

M
      
    
    {\displaystyle M}
  
-acts

设是幺半群而是非空集合。如果存在一个乘法运算
 
它满足性质
，
此处1表幺半群之单位元素，并且
，
对所有和，三元组被称为右-act或简称右-act。一般而言，表示“的元素与的元素的右乘法”。右-act经常写为。
左-act定义类似，即
 
并经常表示为。
一个-act变换半群十分相似，然而的元素本身不必然为函数，它们仅是某个幺半群的元素。所以，必须限制的作用与幺半群中的乘法一致（亦即，），因为一般而言，对于某个任意此性质可能不成立，保证此一致性可使进行函数复合时不致出问题。
一旦加上这种限制，就可以完全放心的去掉所有括号，因为幺半群乘积和幺半群在集合上的作用是完全满足结合性的。特别是这允许了幺半群的元素被表示为计算机科学意义上字母的字符串。这种抽象接着允许谈论一般的字符串运算，并最终导致了由字母的字符串构成的形式语言概念。
-act和变换幺半群的另一个差异在于，对一个-act ，幺半群的两个相异元素可能决定同样的Q变换。若我们限制其发生，则-act与变换幺半群便完全相同。

完全变换幺半群

完全变换幺半群（或完全变换半群）是所有映射的搜集。完全变换幺半群是自由幺半群，在允许所有可能性的意义上。完全变换幺半群的一个特殊情况是置换群。

性质

如果状态集合Q是有限的，则转移函数通常表示为状态转移表。在自由群中字符串所驱动的所有可能转移的构造有一种叫de Bruijn图的图形描述。
状态集合Q不需要是有限的。作为例子，半自动机巩固了量子有限自动机的概念。它的状态集合Q由复投影空间给出，单独状态别称为n-状态qubit。状态转移给出自酉n×n矩阵。输入字母表仍是有限的，而其他自动机理论的典型关键概念仍有效。因此，量子半自动机可简单的定义为三元组当字母表有p个字母的时候，所以对每个字母都有一个酉矩阵。这种方式规定之后，量子半自动机明显有多种几何推广。比如，可以用黎曼对称空间替代，并从它的等距群选出转移函数。
形式语言的语法幺半群同构于到接受这个语言的极小自动机的转移幺半群。

范畴Act

定义右作用的代数关系形成了一个范畴Act。对象是M-act，而范畴的态射是M-同态。