セミオートマトン

数学および理論計算機科学において、半オートマトンとは、入力はあるが出力はない決定論的な有限オートマトンである。これは、状態の集合 Q 、入力アルファベットと呼ばれる集合 Σ 、および遷移関数と呼ばれる 関数T : Q × Σ → Qから構成される。

あらゆるセミオートマトンには、セミオートマトンの特性モノイド、入力モノイド、遷移モノイド、または遷移システムと呼ばれるモノイドが関連付けられており、状態集合Qに作用します。これは、入力アルファベット Σ の文字列の自由モノイドの作用として、またはQの誘導変換半群として見ることができます。

Clifford と Preston (1967) のような古い本では、半群の作用は「オペランド」と呼ばれています。

圏論では、半オートマトンとは本質的には関数である。

変換半群または変換モノイドは、集合Q (「状態の集合」と呼ばれることが多い) と、Q をそれ自身に写像する関数または「変換」の半群またはモノイドMからなるペアです。これらは、 Mのすべての要素mが写像 であるという意味で関数です。 sとt が変換半群の 2 つの関数である場合、それらの半群積は関数合成として定義されます。 ${\displaystyle (M,Q)}$ ${\displaystyle m\colon Q\to Q}$ ${\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}$

一部の著者は、「半群」と「モノイド」を同義語と見なしています。ここで、半群は単位元を持つ必要はありません。モノイドは単位元 (「単位」とも呼ばれる) を持つ半群です。集合に作用する関数の概念には常に単位関数の概念が含まれており、これを集合に適用しても何も起こらないため、変換半群に単位関数を追加することでモノイドにすることができます。

Mをモノイド、Qを空でない集合と する。乗法演算が存在する場合

${\displaystyle \mu \colon Q\times M\to Q}$

${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

これは以下の性質を満たす

${\displaystyle q1=q}$

1はモノイドの単位であり、

${\displaystyle q(st)=(qs)t}$

すべてのおよびに対して が成り立つとき、この 3 つ組は右M行為または単に右行為と呼ばれます。正確に言うと、はQ の要素と M の要素との右乗算です。右行為は と表記されることが多いです。 ${\displaystyle q\in Q}$${\displaystyle s,t\in M}$${\displaystyle (Q,M,\mu )}$${\displaystyle \mu }$${\displaystyle Q_{M}}$

左行為も同様に定義され、

${\displaystyle \mu \colon M\times Q\to Q}$

${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

と表記されることが多いです。 ${\displaystyle \,_{M}Q}$

M作用は変換モノイドと密接に関連しています。しかし、 Mの要素は関数そのものである必要はなく、何らかのモノイドの要素にすぎません。したがって、 の作用はモノイドの乗算と一貫性があることを要求しなければなりません (つまり)。これは一般に、関数合成の場合とは異なり、任意のに対しては成立しない可能性があるためです。 ${\displaystyle \mu }$ ${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$${\displaystyle \mu }$

一度この要求を行えば、モノイド積とモノイドの集合への作用は完全に結合的であるため、括弧を全て削除しても全く問題ありません。特に、これによりモノイドの要素を文字列として表現することが可能になります。これはコンピュータサイエンスの意味で「文字列」を意味します。この抽象化により、文字列操作全般について話すことが可能になり、最終的には文字列で構成される形式言語という概念につながります。 ^{[さらに説明が必要]}

M行為と変換モノイドのもう 1 つの違いは、 M行為Qの場合、モノイドの 2 つの異なる要素がQの同じ変換を決定する可能性があることです。これが発生しないように要求すると、M行為は本質的に変換モノイドと同じになります。

2つのM -行為が同じモノイド を共有する場合、M -準同型写像は次のような 写像である。${\displaystyle Q_{M}}$${\displaystyle B_{M}}$${\displaystyle M}$ ${\displaystyle f\colon Q_{M}\to B_{M}}$${\displaystyle f\colon Q\to B}$

${\displaystyle f(qm)=f(q)m}$

すべてのおよびに対して成り立ちます。すべてのM準同型全体の集合は、一般にまたは と表記されます。 ${\displaystyle q\in Q_{M}}$${\displaystyle m\in M}$${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$${\displaystyle \mathrm {Hom} _{M}(Q,B)}$

M-行為とM-準同型は一緒にM-行為と呼ばれるカテゴリを形成します。^[1]

セミオートマトンとは、入力アルファベットと呼ばれる空でない集合、Qと呼ばれる空でない集合、状態集合と呼ばれる空でない集合、Tが遷移関数である三つ組である。${\displaystyle (Q,\Sigma ,T)}$${\displaystyle \Sigma }$

${\displaystyle T\colon Q\times \Sigma \to Q.}$

状態集合Qが有限集合である場合 (必ずしもそうである必要はありません)、半オートマトンを、初期状態または受け入れ状態集合Aを持たない決定論的有限オートマトン と考えることができます。あるいは、出力がなく、入力のみを持つ 有限状態マシンです。${\displaystyle (Q,\Sigma ,T,q_{0},A)}$${\displaystyle q_{0}}$

任意のセミオートマトンは次の方法でモノイドの動作を誘導します。

をアルファベットによって生成される自由モノイドとします（上付き文字 * はクリーネ星であると理解されます）。これはの文字で構成される有限長の文字列全体の集合です。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$${\displaystyle \Sigma }$

内のすべての単語wに対して、Q内のすべてのqに対して次のように再帰的に定義された関数を とします。 ${\displaystyle \Sigma ^{*}}$${\displaystyle T_{w}\colon Q\to Q}$

• の場合、 となり、空の単語によって状態が変わることはありません。${\displaystyle w=\varepsilon }$${\displaystyle T_{\varepsilon }(q)=q}$ ${\displaystyle \varepsilon }$
• が 内の文字である場合、 となります。${\displaystyle w=\sigma }$${\displaystyle \Sigma }$${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$
• およびの場合、 となります。${\displaystyle w=\sigma v}$${\displaystyle \sigma \in \Sigma }$${\displaystyle v\in \Sigma ^{*}}$${\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}$

集合を ${\displaystyle M(Q,\Sigma ,T)}$

${\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.}$

集合 は関数合成に関して閉じています。つまり、すべての に対してが成り立ちます。また、 にはQ上の恒等関数である も含まれます。関数合成は結合的であるため、集合 はモノイドです。つまり、半オートマトン の入力モノイド、特性モノイド、特性半群、または遷移モノイドと呼ばれます。${\displaystyle M(Q,\Sigma ,T)}$${\displaystyle v,w\in \Sigma ^{*}}$${\displaystyle T_{w}\circ T_{v}=T_{vw}}$${\displaystyle T_{\varepsilon }}$${\displaystyle M(Q,\Sigma ,T)}$${\displaystyle (Q,\Sigma ,T)}$

状態集合Qが有限である場合、遷移関数は一般に状態遷移表として表されます。自由モノイド内の文字列によって駆動されるすべての可能な遷移の構造は、de Bruijn グラフとしてグラフィカルに表現されます。

状態集合Q は有限である必要はなく、可算である必要もありません。例えば、セミオートマトンが量子有限オートマトンの概念の基礎となっています。そこでは、状態集合Qは複素射影空間 によって与えられ、個々の状態はn状態量子ビットと呼ばれます。状態遷移は、ユニタリn × n行列によって与えられます。入力アルファベットは有限のままであり、オートマトン理論の他の典型的な関心事も作用します。したがって、量子セミオートマトンを、アルファベットがp文字で、各文字 に対して1 つのユニタリ行列があるときの3 つ組 として簡単に定義することができます。このように述べると、量子セミオートマトンには多くの幾何学的一般化があります。したがって、たとえば、の代わりにリーマン対称空間を取り、その等長変換群から遷移関数として選択することができます。 ${\displaystyle \mathbb {C} P^{n}}$${\displaystyle \Sigma }$${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})}$${\displaystyle \Sigma }$${\displaystyle U_{\sigma }}$${\displaystyle \sigma \in \Sigma }$${\displaystyle \mathbb {C} P^{n}}$

正規言語の構文モノイドは、その言語を受け入れる最小オートマトンの遷移モノイドと同型です。

• AH CliffordとGB Preston、「半群の代数理論」、アメリカ数学会、第 2 巻 (1967 年)、ISBN  978-0-8218-0272-4。
• F. Gecseg および I. Peak、「オートマトン代数理論」（1972 年）、Akademiai Kiado、ブダペスト。
• WML ホルコム『代数オートマトン理論』（1982 年）、ケンブリッジ大学出版局
• JM Howie、「オートマトンと言語」（1991年）、Clarendon Press、ISBN 0-19-853442-6。 
• Mati Kilp、Ulrich Knauer、Alexander V. Mikhalov、Monoids、Acts and Catalog (2000)、Walter de Gruyter、ベルリン、ISBN 3-11-015248-7。 
• ルドルフ・リドルとギュンター・ピルツ、応用抽象代数(1998)、シュプリンガー、ISBN 978-0-387-98290-8