構文モノイド

数学およびコンピュータ科学において、構文モノイド${\displaystyle M(L)}$形式言語の${\displaystyle L}$は言語を認識する最小モノイドである${\displaystyle L}$マイヒル・ネロードの定理により、構文モノイドは一意同型を除いて一意である。

アルファベットは有限集合である。

与えられたアルファベット上の自由モノイドは、その集合から0個以上の要素からなるすべての文字列を要素とするモノイドであり、文字列の連結がモノイド演算であり、空文字列が単位元である。

部分集合が与えられた場合${\displaystyle S}$自由モノイドの${\displaystyle M}$要素の形式的な左逆または右逆からなる集合を定義することができる。${\displaystyle S}$これらは商と呼ばれ、連結する側に応じて右商または左商を定義できます。したがって、右商は${\displaystyle S}$要素によって${\displaystyle m}$から${\displaystyle M}$セットは

${\displaystyle S\ /\ m=\{u\in M\;\vert \;um\in S\}.}$

同様に、左商は

${\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}.}$

構文商は、${\displaystyle M}$構文関係、または構文等価性と呼ばれる （${\displaystyle S}$)

正しい構文的等価性は等価関係である

${\displaystyle s\sim _{S}t\ \Leftrightarrow \ S\,/\,s\;=\;S\,/\,t\ \Leftrightarrow \ (\forall x\in M\colon \ xs\in S\Leftrightarrow xt\in S)}$。

同様に、左構文等価性は

${\displaystyle s\;{}_{S}{\sim }\;t\ \Leftrightarrow \ s\setminus S\;=\;t\setminus S\ \Leftrightarrow \ (\forall y\in M\colon \ sy\in S\Leftrightarrow ty\in S)}$。

右構文等価性は文字列連結に関して左一致であり、その逆もまた同様であることに注意してください。${\displaystyle s\sim _{S}t\ \Rightarrow \ xs\sim _{S}xt\ }$すべての人々のために${\displaystyle x\in M}$。

構文的一致またはマイヒル一致^{[ 1 ]は[ 2 ]}のように定義される。

${\displaystyle s\equiv _{S}t\ \Leftrightarrow \ (\forall x,y\in M\colon \ xsy\in S\Leftrightarrow xty\in S)}$。

この定義は、部分集合によって定義される合同関係にも適用される。${\displaystyle S}$一般モノイドの${\displaystyle M}$選言集合は部分集合である。${\displaystyle S}$構文的一致が定義されるように${\displaystyle S}$は等号関係である。^{[ 3 ]}

電話をかけましょう${\displaystyle [s]_{S}}$同値類${\displaystyle s}$構文的一致性について。構文的一致性はモノイドにおける連結と両立する。つまり、

${\displaystyle [s]_{S}[t]_{S}=[st]_{S}}$

すべての人々のために${\displaystyle s,t\in M}$したがって、構文商はモノイド射であり、商モノイドを誘導する。

${\displaystyle M(S)=M\ /\ {\equiv _{S}}}$。

このモノイド${\displaystyle M(S)}$は構文モノイドと呼ばれる${\displaystyle S}$。これは、認識する最小のモノイドであることが示せる。${\displaystyle S}$つまり、${\displaystyle M(S)}$認識する${\displaystyle S}$、そしてすべてのモノイドに対して${\displaystyle N}$認識する${\displaystyle S}$、${\displaystyle M(S)}$はサブモノイドの商である${\displaystyle N}$構文モノイド${\displaystyle S}$は、最小オートマトン遷移モノイドでもある。${\displaystyle S}$[ ^{1 ] [ 2 ] [ 4 ]​}

グループ言語とは、構文モノイドがグループである言語のことである。^{[ 5 ]}

• させて${\displaystyle L}$言語を${\displaystyle A=\{a,b\}}$偶数長の単語。構文的一致には 2 つのクラスがあります。${\displaystyle L}$それ自体と${\displaystyle L_{1}}$奇数長の単語。構文モノイドは、上の位数2の群です。${\displaystyle \{L,L_{1}\}}$[ ^{6 ]​}
• 言語については${\displaystyle (ab+ba)^{*}}$最小オートマトンには4つの状態があり、構文モノイドには15の要素がある。^{[ 7 ]}
• 二環式モノイドは、ディック言語（括弧の均衡集合の言語）の構文モノイドである。
• 自由モノイド​${\displaystyle A}$（どこ${\displaystyle \left|A\right|>1}$) は言語の構文モノイドである${\displaystyle \{ww^{R}\mid w\in A^{*}\}}$、 どこ${\displaystyle w^{R}}$は単語の逆です${\displaystyle w}$。 （のために${\displaystyle \left|A\right|=1}$（文字の二乗の法則を用いることもできる。）
• すべての非自明な有限モノイドは、何らかの非自明な言語の構文モノイドと同型であるが、^{[ 8 ]}すべての有限モノイドが構文モノイドと同型であるとは限らない。^{[ 9 ]}
• すべての有限群は、ある正規言語の構文モノイドと同型である。^{[ 8 ]}
• 言語${\displaystyle \{a,b\}}$発生回数${\displaystyle a}$そして${\displaystyle b}$は法で合同である$2n$は構文モノイドを持つ群言語である${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$[ ^{5 ]​}
• トレースモノイドは、構文モノイドの一例である。
• マルセル＝ポール・シュッツェンベルガー^{[ 10 ]}は、スターフリー言語を有限非周期構文モノイドを持つ言語として特徴づけた。^{[ 11 ]}

• アンダーソン、ジェームズ A. (2006).現代的応用を伴うオートマタ理論。トム・ヘッドによる寄稿あり。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-61324-8. Zbl 1127.68049 . 
• Holcombe, WML (1982).代数オートマトン理論. Cambridge Studies in Advanced Mathematics. Vol.  1. Cambridge University Press . ISBN 0-521-60492-3. Zbl 0489.68046 . 
• ローソン、マーク・V. (2004).有限オートマトン. チャップマン・アンド・ホール/CRC. ISBN 1-58488-255-7. Zbl 1086.68074 . 
• Pin, Jean-Éric (1997). "10. 構文半群". Rozenberg, G.; Salomaa, A. (編). Handbook of Formal Language Theory (PDF) . Vol.  1. Springer-Verlag . pp. 679–746 . Zbl 0866.68057 .  
• サカロヴィッチ、ジャック（2009）。オートマタ理論の要素。ルーベン・トーマス訳。ケンブリッジ大学出版局。ISBN 978-0-521-84425-3. Zbl 1188.68177 . 
• ストラウビング、ハワード（1994）。有限オートマトン、形式論理、回路複雑性。理論計算機科学の進歩。バーゼル：ビルクハウザー。ISBN 3-7643-3719-2. Zbl 0816.68086 .