查看“︁语法幺半群”︁的源代码

{{noteTA
|T=zh-cn:语法幺半群; zh-tw:語法么半群;
|1=zh:幺; zh-cn:幺; zh-tw:么;
}}

'''语法幺半群'''，即在[[数学]]中，[[形式语言]] ''L'' 的 '''语法幺半群''' ''M''(''L'') 是[[可识别语言|可识别]]语言 ''L'' 的最小的[[幺半群]]。

==语法商==

给定幺半群 ''M'' 的子集 <math>S\subset M</math>，可以定义由 ''S'' 中元素的形式左逆或右逆组成的集合。它们叫做[[字符串运算|商]]，可以定义右商和左商，依赖于串接的是哪一端。''S'' 与一个元素 <math>m\in M</math> 的'''右商'''是集合
:<math>S/m=\{u\in M \;\vert\; um\in S \}</math>

类似的，'''左商'''是 

:<math>m\setminus S=\{u\in M \;\vert\; mu\in S \}</math>

==语法等价==

语法商引发了 ''M'' 上的一个[[等价关系]]，叫做(引发自 ''S'' 的)'''语法关系'''、'''语法等价'''或'''语法同余'''。右语法等价是等价关系

:<math>\sim_S \;= \{(s,t)\in M\times M \,\vert\; S/s = S/t \}</math>

类似的，左语法关系是

:<math>\,_S\sim \;= \{(s,t)\in M\times M \,\vert\; s\setminus S = t \setminus S \}</math>

两端同余可以定义为

:<math>u \sim_S v \Leftrightarrow \forall x, y\in M (xuy \in S \Leftrightarrow xvy \in S)</math>

==语法幺半群==

语法商相容于在幺半群中的串接，有着

:<math>(M/s)/t = M/(ts) \,</math>

对于所有 <math>s,t\in M</math> (左商也类似)。所以，语法商是[[幺半群态射]]，并包括一个[[商幺半群]]

:<math>M(S)= M / \sim_S \,</math>

可以证明 ''S'' 的语法幺半群是[[可识别语言|可识别]] ''S'' 的最小的幺半群；就是说 ''M''(''S'') 识别 ''S''，对于所有识别 ''S'' 的幺半群 ''N''，''M''(''S'') 是 ''N'' 的[[子幺半群]]的商。''S'' 的语法幺半群也是 ''S'' 的[[极小自动机]]的[[转移幺半群]]。

等价的说，一个语言 ''L'' 是可识别的，当且仅当商的族

:<math>\{L/m \,\vert\; m\in M\}</math>

是有限的。等价性的证明非常容易。假定字符串 ''x'' 是可被[[确定有限状态自动机]]识别的，带有最终机器状态是 ''f''。如果 ''y'' 是这个机器可识别的另一个字符串，也终止于同样的最终状态 ''f''，则明显的有 <math>L/x\,\sim L/y</math>。类似的，在 <math>\{L/m \,\vert\; m\in M\}</math> 中元素的数目就精确等于这个自动机的最终状态的数目。假定反过来: 在 <math>\{L/m \,\vert\; m\in M\}</math> 中元素的数目是有限的。可以接着构造一个自动机，使得 <math>Q=\{L/m \,\vert\; m\in M\}</math> 是状态的集合，<math>F=\{L/m \,\vert\; m\in L\}</math> 是最终状态的集合，单元素集合 ''L'' 是初始状态，转移函数给出自 <math>(L/x)/y=L/(xy)</math>。明显的这个自动机识别 ''L''。所以语言 ''L'' 是可识别的当且仅当集合 <math>\{L/m \,\vert\; m\in M\}</math> 是有限的。

给定表示 ''S'' 的一个[[正则表达式]] ''E''，很容易计算 ''S'' 的语法幺半群。

==例子==
* [[雙循環么半群]]是 [[戴克語]]的语法幺半群。
* [[跡幺半群]]是语法幺半群。

==參考文獻==
* Jean-Eric Pin, [http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf "Syntactic semigroups"]{{Wayback|url=http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf |date=20110517111441 }}, Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679-746

[[Category:形式语言|Y]]
[[Category:半群论|Y]]