语法幺半群

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

语法商

给定幺半群 M 的子集 ${\displaystyle S\subset M}$ ，可以定义由 S 中元素的形式左逆或右逆组成的集合。它们叫做商，可以定义右商和左商，依赖于串接的是哪一端。S 与一个元素 ${\displaystyle m\in M}$  的右商是集合

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

类似的，左商是

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

语法等价

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

${\displaystyle \sim _{S}\;=\{(s,t)\in M\times M\,\vert \;S/s=S/t\}}$ 

类似的，左语法关系是

${\displaystyle \,_{S}\sim \;=\{(s,t)\in M\times M\,\vert \;s\setminus S=t\setminus S\}}$ 

两端同余可以定义为

${\displaystyle u\sim _{S}v\Leftrightarrow \forall x,y\in M(xuy\in S\Leftrightarrow xvy\in S)}$ 

语法幺半群

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

${\displaystyle (M/s)/t=M/(ts)\,}$ 

对于所有 ${\displaystyle s,t\in M}$  (左商也类似)。所以，语法商是幺半群态射，并包括一个商幺半群

${\displaystyle M(S)=M/\sim _{S}\,}$ 

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

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

${\displaystyle \{L/m\,\vert \;m\in M\}}$ 

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

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

例子

• 雙循環么半群是 戴克語的语法幺半群。
• 跡幺半群是语法幺半群。

參考文獻

• Jean-Eric Pin, "Syntactic semigroups"（页面存档备份，存于互联网档案馆）, Chapter 10 in "Handbook of Formal Language Theory", Vol. 1, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997) Vol. 1, pp. 679-746