語法么半群

語法么半群，即在數學中，形式語言 L 的 語法么半群 M(L) 是可識別語言 L 的最小的么半群。

語法商

給定么半群 M 的子集 $S\subset M$，可以定義由 S 中元素的形式左逆或右逆組成的集合。它們叫做商，可以定義右商和左商，依賴於串接的是哪一端。S 與一個元素 $m\in M$ 的右商是集合

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

類似的，左商是

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

語法等價

語法商引發了 M 上的一個等價關係，叫做(引發自 S 的)語法關係、語法等價或語法同餘。右語法等價是等價關係

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

類似的，左語法關係是

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

兩端同餘可以定義為

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

語法么半群

語法商相容於在么半群中的串接，有著

$(M/s)/t=M/(ts)\,$

對於所有 $s,t\in M$ (左商也類似)。所以，語法商是么半群態射，並包括一個商么半群

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

可以證明 S 的語法么半群是可識別 S 的最小的么半群；就是說 M(S) 識別 S，對於所有識別 S 的么半群 N，M(S) 是 N 的子么半群的商。S 的語法么半群也是 S 的極小自動機的轉移么半群。

等價的說，一個語言 L 是可識別的，若且唯若商的族

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

是有限的。等價性的證明非常容易。假定字符串 x 是可被確定有限狀態自動機識別的，帶有最終機器狀態是 f。如果 y 是這個機器可識別的另一個字符串，也終止於同樣的最終狀態 f，則明顯的有 $L/x\,\sim L/y$。類似的，在 $\{L/m\,\vert \;m\in M\}$ 中元素的數目就精確等於這個自動機的最終狀態的數目。假定反過來: 在 $\{L/m\,\vert \;m\in M\}$ 中元素的數目是有限的。可以接著構造一個自動機，使得 $Q=\{L/m\,\vert \;m\in M\}$ 是狀態的集合，$F=\{L/m\,\vert \;m\in L\}$ 是最終狀態的集合，單元素集合 L 是初始狀態，轉移函數給出自 $(L/x)/y=L/(xy)$。明顯的這個自動機識別 L。所以語言 L 是可識別的若且唯若集合 $\{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