語法幺半群
語法幺半群
語法幺半群,即在數學中,形式語言 L 的 語法幺半群 M(L) 是可識別語言 L 的最小的幺半群。
![語法幺半群](https://i1.twwiki.net/cover/w200/me/f/mef7a6eb45b75745b8af4d88f2df632da.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/mc/3/mc326439c690f0c596654873461f5a1c2.jpg)
語法幺半群
給定幺半群M的子集,可以定義由S中元素的形式左逆或右逆組成的集合。它們叫做商,可以定義右商和左商,依賴於串接的是哪一端。S與一個元素 的 右商是集合
![語法幺半群](https://i1.twwiki.net/cover/w200/mb/b/mbbc561cb2455a7b98eb429e6e55a4f31.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/mc/6/mc636b12490ef41092b545918a0c79030.jpg)
語法幺半群
語法商引發了M上的一個等價關係,叫做(引發自S的) 語法關係、語法等價或 語法同餘。右語法等價是等價關係
![語法幺半群](https://i1.twwiki.net/cover/w200/m7/b/m7ba343091723c4db983490fd553cc294.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m0/e/m0e45557d79c7684adaa4419e307f9f08.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m6/2/m628ca6d121b042c9e954e93b57a1747b.jpg)
語法幺半群
語法商相容於在幺半群中的串接,有著
![語法幺半群](https://i1.twwiki.net/cover/w200/mf/a/mfaab6b8a628b6e6824d474f0c4de23be.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m9/b/m9b6a6c3d06a9279b8744b03e4186eeef.jpg)
語法幺半群
對於所有 (左商也類似)。所以,語法商是幺半群態射,並包括一個商幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m1/c/m1cab2fd175fc434b9444f406e4760c1f.jpg)
語法幺半群
等價的說,一個語言L是可識別的,當且僅當商的族
![語法幺半群](https://i1.twwiki.net/cover/w200/mf/d/mfddf50067da7fe8859a472b60df9a95d.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m6/5/m652ee67df75d2b1b41e4741c810f0a68.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m4/d/m4d8772813d89b43b0794165ae6d34fe3.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m4/d/m4d8772813d89b43b0794165ae6d34fe3.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m9/7/m97f85576b990a669268420c12e529b60.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m6/1/m617ce6171508498bd4c4ed745ddaa0d8.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m5/7/m57c4ac89c8f5f45ac574d71b70d537c2.jpg)
語法幺半群
![語法幺半群](https://i1.twwiki.net/cover/w200/m4/d/m4d8772813d89b43b0794165ae6d34fe3.jpg)
語法幺半群
是有限的。等價性的證明非常容易。假定字元串x是可被確定有限狀態自動機識別的,帶有最終機器狀態是f。如果y是這個機器可識別的另一個字元串,也終止於同樣的最終狀態f,則明顯的有。類似的,在 中元素的數目就精確等於這個自動機的最終狀態的數目。假定反過來: 在 中元素的數目是有限的。可以接著構造一個自動機,使得 是狀態的集合,是最終狀態的集合,單元素集合L是初始狀態,轉移函數給出自。明顯的這個自動機識別L。所以語言L是可識別的當且僅當集合 是有限的。
給定表示S的一個正則表達式E,很容易計算S的語法幺半群。
• 雙循環幺半群是戴克語的語法幺半群。
• 跡幺半群是語法幺半群。