语法幺半群,即在数学中,形式语言 L 的 语法幺半群 M(L) 是可识别语言 L 的最小的幺半群。
语法商
给定幺半群 M 的子集
,可以定义由 S 中元素的形式左逆或右逆组成的集合。它们叫做商,可以定义右商和左商,依赖于串接的是哪一端。S 与一个元素
的右商是集合
![{\displaystyle S/m=\{u\in M\;\vert \;um\in S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/657a391a3ae04ad996e72cdfb30d1bcec976f783)
类似的,左商是
![{\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/9d3aab6727cc822ca4736840f45613f79d3dc44b)
语法等价
语法商引发了 M 上的一个等价关系,叫做(引发自 S 的)语法关系、语法等价或语法同余。右语法等价是等价关系
![{\displaystyle \sim _{S}\;=\{(s,t)\in M\times M\,\vert \;S/s=S/t\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/1e870836ca518f36e719de5d1c853c60af704e2e)
类似的,左语法关系是
![{\displaystyle \,_{S}\sim \;=\{(s,t)\in M\times M\,\vert \;s\setminus S=t\setminus S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e73e334c80bf4c070ad83b4a41aba9253ba42d6b)
两端同余可以定义为
![{\displaystyle u\sim _{S}v\Leftrightarrow \forall x,y\in M(xuy\in S\Leftrightarrow xvy\in S)}](//wikimedia.org/api/rest_v1/media/math/render/svg/bf77dd4ecfcae36f3dd3485fe343bcf87a6b679b)
语法幺半群
语法商相容于在幺半群中的串接,有着
![{\displaystyle (M/s)/t=M/(ts)\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/525196708bc0f6638e893c779c0e948c8778acdb)
对于所有
(左商也类似)。所以,语法商是幺半群态射,并包括一个商幺半群
![{\displaystyle M(S)=M/\sim _{S}\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/54fece64a93db6ba6c7852a1ef5783445675cf8a)
可以证明 S 的语法幺半群是可识别 S 的最小的幺半群;就是说 M(S) 识别 S,对于所有识别 S 的幺半群 N,M(S) 是 N 的子幺半群的商。S 的语法幺半群也是 S 的极小自动机的转移幺半群。
等价的说,一个语言 L 是可识别的,当且仅当商的族
![{\displaystyle \{L/m\,\vert \;m\in M\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/f17c1fd5c4ccedaae1c90443cc6ddc966c2d480a)
是有限的。等价性的证明非常容易。假定字符串 x 是可被确定有限状态自动机识别的,带有最终机器状态是 f。如果 y 是这个机器可识别的另一个字符串,也终止于同样的最终状态 f,则明显的有
。类似的,在
中元素的数目就精确等于这个自动机的最终状态的数目。假定反过来: 在
中元素的数目是有限的。可以接着构造一个自动机,使得
是状态的集合,
是最终状态的集合,单元素集合 L 是初始状态,转移函数给出自
。明显的这个自动机识别 L。所以语言 L 是可识别的当且仅当集合
是有限的。
给定表示 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