語法么半群

語法商

給定么半群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的語法么半群。