語法幺半群

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

類似的，左商是

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

類似的，左語法關係是

兩端同餘可以定義為

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

對於所有 (左商也類似)。所以，語法商是幺半群態射，並包括一個商幺半群

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

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

是有限的。等價性的證明非常容易。假定字元串x是可被確定有限狀態自動機識別的，帶有最終機器狀態是f。如果y是這個機器可識別的另一個字元串，也終止於同樣的最終狀態f，則明顯的有。類似的，在 中元素的數目就精確等於這個自動機的最終狀態的數目。假定反過來: 在 中元素的數目是有限的。可以接著構造一個自動機，使得 是狀態的集合，是最終狀態的集合，單元素集合L是初始狀態，轉移函數給出自。明顯的這個自動機識別L。所以語言L是可識別的當且僅當集合 是有限的。

給定表示S的一個正則表達式E，很容易計算S的語法幺半群。

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

• 跡幺半群是語法幺半群。