语法幺半群

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

给定幺半群 的子集 ${\displaystyle S\subset <!--\; \subset \; -->M}$ 中元素的形式左逆或右逆组成的集合。它们叫做商，可以定义右商和左商，依赖于串接的是哪一端。 与一个元素 ${\displaystyle m\in <!--\; \in \; -->M}$ 上的一个等价关系，叫做(引发自 的)语法关系、语法等价或语法同余。右语法等价是等价关系

类似的，左语法关系是

两端同余可以定义为

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

对于所有 ${\displaystyle s,t\in <!--\; \in \; -->M}$ 的语法幺半群是可识别 的最小的幺半群；就是说 () 识别 ，对于所有识别 的幺半群 ，() 是 的子幺半群的商。 的语法幺半群也是 的极小自动机的转移幺半群。

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

是有限的。等价性的证明非常容易。假定字符串 是可被确定有限状态自动机识别的，带有最终机器状态是 。如果 是这个机器可识别的另一个字符串，也终止于同样的最终状态 ，则明显的有 ${\displaystyle L/x\sim <!--\; \sim \; -->L/y}$ 是初始状态，转移函数给出自 ${\displaystyle (L/x)/y=L/(xy)}$。所以语言 是可识别的当且仅当集合 ${\displaystyle \{L/m|m\in <!--\; \in \; -->M\}}$ 的一个正则表达式 ，很容易计算 的语法幺半群。