半自动机 目录 变换半群 Mdisplaystyle M-acts 完全变换幺半群 半自动机 M-同态 性质 范畴Act 引用 导航菜单Associative Digital Network Theory
自动机形式语言半群论
数学计算机科学幺半群代数结构群作用自动机范畴论作用函子集合狀態函數幺半群半群函數複合恒等函数幺半群集合结合性字符串字符串运算形式语言自由幺半群置换群确定有限自动机有限状态自动机字母表自由幺半群Kleene星号字符串函数复合恒等函数结合性状态转移表de Bruijn图量子有限自动机复投影空间qubit酉n×n矩阵黎曼对称空间形式语言语法幺半群同构极小自动机范畴对象态射
在数学和计算机科学中，半自动机或Mdisplaystyle M-act是幺半群在集合上的乘法性运算。从代数结构的观点来看，它非常接近于群作用的概念。从计算机科学的观点来看，它是只有输入没有输出的自动机。从范畴论的观点来看，作用是如范畴上的函子般重要。
这个概念也叫做S-集合、M-集合、M-操作数、S-系统、S-自动机、转移系统、算子幺半群、变换半群或转移幺半群。本文力图表现出它们表示的是同一个概念，尽管在使用中有各种概念和术语的变体。
目录
1 变换半群
2 Mdisplaystyle M-acts
3 完全变换幺半群
4 半自动机
5 M-同态
6 性质
7 范畴Act
8 引用
变换半群
變換半群或變換幺半群是由集合Qdisplaystyle Q（通常稱為“狀態集合”），和映射Qdisplaystyle Q到自身的函數或“變換”Mdisplaystyle M之幺半群或半群構成的有序对(M,Q)displaystyle (M,Q)。此類函數意指Mdisplaystyle M中的每個元素mdisplaystyle m均為一m:Q→Qdisplaystyle m:Qto Q映射。若sdisplaystyle s和tdisplaystyle t是這個變換半群的兩個不同函數，則半群乘積可直覺地由函數複合得出，故吾人將(st)(q)displaystyle (st)(q)定義為(s∘t)(q)=s(t(q))displaystyle (scirc t)(q)=s(t(q))。
注意“半群”與“幺半群”的使用：有些作者將“半群”與“幺半群”視為同義詞。然而此處一個半群不必然包含單位元素；而一個幺半群則意指含有單位元素的半群。因為作用於集合上的函數概念永遠包括恒等函数概念在內，亦即施加於集合上時不做任何動作，故變換半群可藉由與恒等函數聯集轉為幺半群。
Mdisplaystyle M-acts
设Mdisplaystyle M是幺半群而Qdisplaystyle Q是非空集合。如果存在一个乘法运算
μ:Q×M→Qdisplaystyle mu :Qtimes Mto Q
(q,m)↦qm=μ(q,m)displaystyle (q,m)mapsto qm=mu (q,m)
它满足性质
q1=qdisplaystyle q1=q，
此處1表幺半群之單位元素，並且
q(st)=(qs)tdisplaystyle q(st)=(qs)t，
对所有q∈Qdisplaystyle qin Q和s,t∈Mdisplaystyle s,tin M，三元组(Q,M,μ)displaystyle (Q,M,mu )被称为右Mdisplaystyle M-act或简稱右-act。一般而言，μdisplaystyle mu 表示“Qdisplaystyle Q的元素与Mdisplaystyle M的元素的右乘法”。右-act经常写为QMdisplaystyle Q_M。
左-act定义类似，即
μ:M×Q→Qdisplaystyle mu :Mtimes Qto Q
(m,q)↦mq=μ(m,q)displaystyle (m,q)mapsto mq=mu (m,q)
并经常表示为MQdisplaystyle ,_MQ。
一個Mdisplaystyle M-act变换半群十分相似，然而Mdisplaystyle M的元素本身不必然為函数，它们僅是某个幺半群的元素。所以，必须限制μdisplaystyle mu 的作用與幺半群中的乘法一致（亦即，μ(q,st)=μ(μ(q,s),t)displaystyle mu (q,st)=mu (mu (q,s),t)），因为一般而言，对于某个任意μdisplaystyle mu 此性質可能不成立，保證此一致性可使進行函數複合時不致出問題。
一旦加上这种限制，就可以完全放心的去掉所有括号，因为幺半群乘积和幺半群在集合上的作用是完全滿足结合性的。特别是这允许了幺半群的元素被表示为计算机科学意义上字母的字符串。这种抽象接着允许谈论一般的字符串运算，并最终导致了由字母的字符串构成的形式语言概念。
Mdisplaystyle M-act和變換幺半群的另一個差異在於，對一個Mdisplaystyle M-act Qdisplaystyle Q，幺半群的兩個相異元素可能決定同樣的Q變換。若我們限制其發生，則Mdisplaystyle M-act與變換幺半群便完全相同。
完全变换幺半群
完全变换幺半群（或完全变换半群）是所有映射m:Q→Qdisplaystyle m:Qto Q的搜集。完全变换幺半群是自由幺半群，在允许所有可能性的意义上。完全变换幺半群的一个特殊情况是置换群。
半自动机
半自动机是三元组(Q,Σ,T)displaystyle (Q,Sigma ,T)，这里的Σdisplaystyle Sigma 是叫做“输入字母表”的非空集合，Q是叫做“状态集合”的非空集合，而T是“转移函数”，
- T:Q×Σ→Qdisplaystyle T:Qtimes Sigma to Q
当状态集合Q是有限集合（不是必须的!）的时候，半自动机可以被认为是确定有限自动机(Q,Σ,T,q0,A)displaystyle (Q,Sigma ,T,q_0,A)，但是没有“初始状态” q0displaystyle q_0或“接受状态”的集合A。它还可以被认为是没有输出只有输入的有限状态自动机。
幺半群理论的一个主要主张是半自动机等价于act；所以对于任何act，都有一个唯一的半自动机，或反过来说，对于任何半自动机，都有一个唯一的act。这可以如下这样证实。
设Σ∗displaystyle Sigma ^*是从字母表Σdisplaystyle Sigma 生成的自由幺半群，（上标* 要被理解为是Kleene星号）；它是由在Σdisplaystyle Sigma 中字母构成的所有有限长度字符串的集合。
对于所有Σ∗displaystyle Sigma ^*中的字w，设Tw:Q→Qdisplaystyle T_w:Qto Q是如下递归定义的函数，对于所有Q中的q:
- 如果w=εdisplaystyle w=varepsilon ，则Tε(q)=qdisplaystyle T_varepsilon (q)=q，所以空字εdisplaystyle varepsilon 不改变状态。
- 如果w=σdisplaystyle w=sigma 是Σdisplaystyle Sigma 中的字母，则Tσ(q)=T(q,σ)displaystyle T_sigma (q)=T(q,sigma )。
- 如果w=σvdisplaystyle w=sigma v对于σ∈Σdisplaystyle sigma in Sigma 和v∈Σ∗displaystyle vin Sigma ^*，则Tw(q)=Tv(Tσ(q))displaystyle T_w(q)=T_v(T_sigma (q))。
设M(Q,Σ,T)displaystyle M(Q,Sigma ,T)是个集合
- M(Q,Σ,T)=Twdisplaystyle M(Q,Sigma ,T)=T_wvert win Sigma ^*
集合M(Q,Σ,T)displaystyle M(Q,Sigma ,T)在函数复合下闭合；就是说，对于所有v,w∈Σ∗displaystyle v,win Sigma ^*，有着Tw∘Tv=Tvwdisplaystyle T_wcirc T_v=T_vw。它还包含Tεdisplaystyle T_varepsilon ，它是S上的恒等函数。因为函数复合根据定义是结合性的，集合M(Q,Σ,T)displaystyle M(Q,Sigma ,T)是幺半群：它叫做半自动机(Q,Σ,T)displaystyle (Q,Sigma ,T)的输入幺半群、特征幺半群、特征半群或转移幺半群。
M-同态
M-同态是映射
- f:QM→BMdisplaystyle f:Q_Mto B_M
使得
- f(qm)=f(q)mdisplaystyle f(qm)=f(q)m
对于所有q∈Qdisplaystyle qin Q和m∈Mdisplaystyle min M。所有M-同态的集合通常写为Hom(QM,BM)displaystyle mathrm Hom (Q_M,B_M)或HomM(Q,B)displaystyle mathrm Hom _M(Q,B)。
性质
如果状态集合Q是有限的，则转移函数通常表示为状态转移表。在自由群中字符串所驱动的所有可能转移的构造有一种叫de Bruijn图的图形描述。
状态集合Q不需要是有限的。作为例子，半自动机巩固了量子有限自动机的概念。它的状态集合Q由复投影空间CPndisplaystyle mathbb C P^n给出，单独状态别称为n-状态qubit。状态转移给出自酉n×n矩阵。输入字母表Σdisplaystyle Sigma 仍是有限的，而其他自动机理论的典型关键概念仍有效。因此，量子半自动机可简单的定义为三元组(CPn,Σ,Uσ1,Uσ2,⋯,Uσp,)displaystyle (mathbb C P^n,Sigma ,U_sigma _1,U_sigma _2,cdots ,U_sigma _p,)当字母表Σdisplaystyle Sigma 有p个字母的时候，所以对每个字母σ∈Σdisplaystyle sigma in Sigma 都有一个酉矩阵Uσdisplaystyle U_sigma 。这种方式规定之后，量子半自动机明显有多种几何推广。比如，可以用黎曼对称空间替代CPndisplaystyle 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.
