语法幺半群
语法商编辑
给定幺半群 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 的语法幺半群。
例子编辑
- 雙循環么半群是 戴克語的语法幺半群。
- 跡幺半群是语法幺半群。
參考文獻编辑
- 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
🔥 Top keywords: Baike: 首页Special:搜索2024年湯姆斯盃淚之女王九龍城寨之圍城歐倩怡郭晉安逆天奇案22024年優霸盃背着善宰跑不夠善良的我們金智媛余苑綺時代力量分裂危機春色寄情人貴婦奈奈台灣抗日運動金秀賢 (男演員)余天九龍寨城嫦娥六号习近平邊佑錫汤姆斯杯六四事件宁安如梦WIND BREAKER—防風少年—排球少年!!角色列表Seventeen (組合)笑看風雲ILLIT乘風2024排球少年!!五億高中生命案范浩揚劉緯民BABYMONSTER城市猎人 (2024年电影)破墓劉俊謙 (香港)中華民國與鳳行中华人民共和国朴成焄梅龍高速公路塌陷事故Energy (組合)支配物种城市猎人BOYNEXTDOOR承欢记白鹿 (演員)逆天奇案五四运动沒有秘密許瑋甯哥吉拉-1.0照明商店 (电影)IVE (組合)迷宮飯周處除三害 (電影)香港周雨彤母亲节金惠奫紀寶如葬送的芙莉蓮打天下2无用的谎言日本草榴社区P站国际劳动节怪獸8號杰伦·布伦森家族榮耀之繼承者鈴木亮平鄧麗君張文傑搜查班長1958福建號航空母艦(G)I-DLE李现李主儐幕府將軍 (2024年電視劇)張員瑛毛泽东星汉灿烂·月升沧海張韶涵三流之路澄碧邨中國國民黨五月天許冠英林依晨文化大革命關於我轉生變成史萊姆這檔事角色列表帝國浩劫:美國內戰三体 (小说)梅龙高速公路