語法幺半羣

給定幺半羣M的子集

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

的右商是集合

類似的，左商是

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

類似的，左語法關係是

兩端同餘可以定義為

語法商相容於在幺半羣中的串接，有着 ^[1] 

對於所有

(左商也類似)。所以，語法商是幺半羣態射，幷包括一個商幺半羣

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

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

是有限的。等價性的證明非常容易。假定字符串x是可被確定有限狀態自動機識別的，帶有最終機器狀態是f。如果y是這個機器可識別的另一個字符串，也終止於同樣的最終狀態f，則明顯的有

。類似的，在

中元素的數目就精確等於這個自動機的最終狀態的數目。假定反過來: 在

中元素的數目是有限的。可以接着構造一個自動機，使得

是狀態的集合，

是最終狀態的集合，單元素集合L是初始狀態，轉移函數給出自

。明顯的這個自動機識別L。所以語言L是可識別的當且僅當集合

是有限的。

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