語法么半群

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

語法商

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

 

類似的,左商

 

語法等價

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

 

類似的,左語法關係是

 

兩端同餘可以定義為

 

語法么半群

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

 

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

 

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

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

 

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

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

例子

參考文獻