查看“︁半自动机”︁的源代码

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

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

==变换半群==

'''變換半群'''或'''變換幺半群'''是由[[集合 (数学)|集合]]<math>Q</math>（通常稱為“[[狀態]]集合”），和映射<math>Q</math>到自身的[[函數]]或“變換”<math>M</math>之[[幺半群]]或[[半群]]構成的有序对<math>(M,Q)</math>。此類函數意指<math>M</math>中的每個元素<math>m</math>均為一<math>m:Q\to Q</math>映射。若<math>s</math>和<math>t</math>是這個變換半群的兩個不同函數，則半群乘積可直覺地由[[函數複合]]得出，故吾人將<math>(st)(q)</math>定義為<math>(s\circ t)(q)=s(t(q))</math>。

注意“半群”與“幺半群”的使用：有些作者將“半群”與“幺半群”視為同義詞。然而此處一個半群不必然包含單位元素；而一個幺半群則意指含有單位元素的半群。因為作用於集合上的函數概念永遠包括[[恒等函数]]概念在內，亦即施加於集合上時不做任何動作，故變換半群可藉由與恒等函數聯集轉為幺半群。

== <math>M</math>-acts ==

设<math>M</math>是[[幺半群]]而<math>Q</math>是非空[[集合 (数学)|集合]]。如果存在一个乘法运算

<math>\mu: Q\times M \to Q</math>
<math>(q,m)\mapsto qm=\mu(q,m)</math>

它满足性质

<math>q1=q </math>，

此處1表幺半群之單位元素，並且

<math>q(st)=(qs)t </math>， 

对所有<math>q\in Q</math>和<math>s,t\in M</math>，三元组<math>(Q,M,\mu)</math>被称为'''右<math>M</math>-act'''或简稱'''右-act'''。一般而言，<math>\mu</math>表示“<math>Q</math>的元素与<math>M</math>的元素的右乘法”。右-act经常写为<math>Q_M</math>。

'''左-act'''定义类似，即

<math>\mu: M\times Q \to Q</math>
<math>(m,q)\mapsto mq=\mu(m,q)</math>

并经常表示为<math>\,_MQ</math>。 

一個<math>M</math>-act变换半群十分相似，然而<math>M</math>的元素本身不必然為函数，它们僅是某个幺半群的元素。所以，必须限制<math>\mu</math>的作用與幺半群中的乘法一致（亦即，<math>\mu(q, st)=\mu(\mu(q,s),t)</math>），因为一般而言，对于某个任意<math>\mu</math>此性質可能不成立，保證此一致性可使進行函數複合時不致出問題。

一旦加上这种限制，就可以完全放心的去掉所有括号，因为幺半群乘积和幺半群在集合上的作用是完全滿足[[结合律|结合性]]的。特别是这允许了幺半群的元素被表示为计算机科学意义上字母的[[字符串]]。这种抽象接着允许谈论一般的[[字符串运算]]，并最终导致了由字母的字符串构成的[[形式语言]]概念。

<math>M</math>-act和變換幺半群的另一個差異在於，對一個<math>M</math>-act <math>Q</math>，幺半群的兩個相異元素可能決定同樣的Q變換。若我們限制其發生，則<math>M</math>-act與變換幺半群便完全相同。

==完全变换幺半群==

'''完全变换幺半群'''（或'''完全变换半群'''）是所有映射<math>m:Q\to Q</math>的搜集。完全变换幺半群是[[自由幺半群]]，在允许所有可能性的意义上。完全变换幺半群的一个特殊情况是[[置换群]]。

==半自动机==

'''半自动机'''是三元组<math>(Q,\Sigma,T) </math>，这里的<math>\Sigma</math>是叫做“输入字母表”的非空集合，''Q''是叫做“状态集合”的非空集合，而''T''是“转移函数”，

:<math>T: Q\times \Sigma \to Q</math>

当状态集合''Q''是有限集合（不是必须的!）的时候，半自动机可以被认为是[[确定有限状态自动机|确定有限自动机]]<math>(Q,\Sigma,T,q_0,A)</math>，但是没有“初始状态” <math>q_0</math>或“接受状态”的集合''A''。它还可以被认为是没有输出只有输入的[[有限状态自动机]]。

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

设<math>\Sigma^*</math>是从[[字母表 (计算机科学)|字母表]]<math>\Sigma</math>生成的[[自由幺半群]]，（上标* 要被理解为是[[Kleene星号]]）；它是由在<math>\Sigma</math>中字母构成的所有有限长度[[字符串]]的集合。

对于所有<math>\Sigma^*</math>中的字''w''，设<math>T_w:Q\to Q</math>是如下递归定义的函数，对于所有''Q''中的''q'':

* 如果<math>w=\varepsilon</math>，则<math>T_\varepsilon (q)=q</math>，所以[[空串|空字]]<math>\varepsilon</math>不改变状态。

* 如果<math>w=\sigma</math>是<math>\Sigma</math>中的字母，则<math>T_\sigma (q)=T(q,\sigma)</math>。

* 如果<math>w=\sigma v</math>对于<math>\sigma\in\Sigma</math>和<math>v\in \Sigma^*</math>，则<math>T_w (q)=T_v(T_\sigma(q))</math>。

设<math>M(Q,\Sigma,T)</math>是个集合 

:<math>M(Q,\Sigma,T)=\{T_w \vert w\in\Sigma^* \}</math> 

集合<math>M(Q,\Sigma,T)</math>在[[函数复合]]下闭合；就是说，对于所有<math>v,w\in\Sigma^*</math>，有着<math>T_w\circ T_v=T_{vw}</math>。它还包含<math>T_\varepsilon</math>，它是''S''上的[[恒等函数]]。因为函数复合根据定义是[[结合律|结合性]]的，集合<math>M(Q,\Sigma,T)</math>是幺半群：它叫做半自动机<math>(Q,\Sigma,T)</math>的'''输入幺半群'''、'''特征幺半群'''、'''特征半群'''或'''转移幺半群'''。

==M-同态==

'''''M''-同态'''是映射

:<math>f:Q_M\to B_M</math>

使得

:<math>f (qm)=f (q)m</math>

对于所有<math>q\in Q</math>和<math>m\in M</math>。所有''M''-同态的集合通常写为<math>\mathrm{Hom}(Q_M, B_M)</math>或<math>\mathrm{Hom}_M(Q, B)</math>。

==性质==

如果状态集合''Q''是有限的，则转移函数通常表示为[[状态转移表]]。在自由群中字符串所驱动的所有可能转移的构造有一种叫[[de Bruijn图]]的图形描述。

状态集合''Q''不需要是有限的。作为例子，半自动机巩固了[[量子有限自动机]]的概念。它的状态集合''Q''由[[复投影空间]]<math>\mathbb{C}P^n</math>给出，单独状态别称为''n''-状态[[qubit]]。状态转移给出自[[酉矩阵|酉''n''×''n''矩阵]]。输入字母表<math>\Sigma</math>仍是有限的，而其他自动机理论的典型关键概念仍有效。因此，'''量子半自动机'''可简单的定义为三元组<math>(\mathbb{C}P^n,\Sigma,\{U_{\sigma_1},U_{\sigma_2},\cdots,U_{\sigma_p},\})</math>当字母表<math>\Sigma</math>有''p''个字母的时候，所以对每个字母<math>\sigma\in\Sigma</math>都有一个酉矩阵<math>U_\sigma</math>。这种方式规定之后，量子半自动机明显有多种几何推广。比如，可以用[[黎曼对称空间]]替代<math>\mathbb{C}P^n</math>，并从它的等距群选出转移函数。

[[形式语言]]的[[语法幺半群]][[同构]]于到接受这个语言的[[极小自动机]]的转移幺半群。

==范畴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]], ''[http://piazza.iae.nl/users/benschop/preface.htm Associative Digital Network Theory]{{Wayback|url=http://piazza.iae.nl/users/benschop/preface.htm |date=20070927235243 }} An Associative Algebra Approach to Logic, Arithmetic and State Machines''（2003）Amspade Research, Geldrop, The Netherlands.

[[Category:自动机|B]]
[[Category:形式语言|B]]
[[Category:半群论|B]]