語法么半群,即在數學中,形式語言 L 的 語法么半群 M(L) 是可識別語言 L 的最小的么半群。
語法商
給定么半群 M 的子集
,可以定義由 S 中元素的形式左逆或右逆組成的集合。它們叫做商,可以定義右商和左商,依賴於串接的是哪一端。S 與一個元素
的右商是集合
![{\displaystyle S/m=\{u\in M\;\vert \;um\in S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/657a391a3ae04ad996e72cdfb30d1bcec976f783)
類似的,左商是
![{\displaystyle m\setminus S=\{u\in M\;\vert \;mu\in S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/9d3aab6727cc822ca4736840f45613f79d3dc44b)
語法等價
語法商引發了 M 上的一個等價關係,叫做(引發自 S 的)語法關係、語法等價或語法同餘。右語法等價是等價關係
![{\displaystyle \sim _{S}\;=\{(s,t)\in M\times M\,\vert \;S/s=S/t\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/1e870836ca518f36e719de5d1c853c60af704e2e)
類似的,左語法關係是
![{\displaystyle \,_{S}\sim \;=\{(s,t)\in M\times M\,\vert \;s\setminus S=t\setminus S\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e73e334c80bf4c070ad83b4a41aba9253ba42d6b)
兩端同餘可以定義為
![{\displaystyle u\sim _{S}v\Leftrightarrow \forall x,y\in M(xuy\in S\Leftrightarrow xvy\in S)}](//wikimedia.org/api/rest_v1/media/math/render/svg/bf77dd4ecfcae36f3dd3485fe343bcf87a6b679b)
語法么半群
語法商相容於在么半群中的串接,有着
![{\displaystyle (M/s)/t=M/(ts)\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/525196708bc0f6638e893c779c0e948c8778acdb)
對於所有
(左商也類似)。所以,語法商是么半群態射,並包括一個商么半群
![{\displaystyle M(S)=M/\sim _{S}\,}](//wikimedia.org/api/rest_v1/media/math/render/svg/54fece64a93db6ba6c7852a1ef5783445675cf8a)
可以證明 S 的語法么半群是可識別 S 的最小的么半群;就是說 M(S) 識別 S,對於所有識別 S 的么半群 N,M(S) 是 N 的子么半群的商。S 的語法么半群也是 S 的極小自動機的轉移么半群。
等價的說,一個語言 L 是可識別的,若且唯若商的族
![{\displaystyle \{L/m\,\vert \;m\in M\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/f17c1fd5c4ccedaae1c90443cc6ddc966c2d480a)
是有限的。等價性的證明非常容易。假定字符串 x 是可被確定有限狀態自動機識別的,帶有最終機器狀態是 f。如果 y 是這個機器可識別的另一個字符串,也終止於同樣的最終狀態 f,則明顯的有
。類似的,在
中元素的數目就精確等於這個自動機的最終狀態的數目。假定反過來: 在
中元素的數目是有限的。可以接着構造一個自動機,使得
是狀態的集合,
是最終狀態的集合,單元素集合 L 是初始狀態,轉移函數給出自
。明顯的這個自動機識別 L。所以語言 L 是可識別的若且唯若集合
是有限的。
給定表示 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