?法?半群 ，?在 ?? 中， 形式?言 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