Thompson构造法

✍ dations ◷ 2025-04-26 17:28:28 #自动机,形式语言,算法

Thompson构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机(NFA)的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式,这也是正则表达式引擎实现的基本思路之一。

正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和替换”以及许多编程语言中,人们都习惯使用正则表达式来表示字符串的匹配模式。然而,当计算机执行匹配程序时,NFA却是更加适合的一种格式。因此,Thompson构造法有着重要的应用价值,它实际上可以视作正则表达式到NFA的一个编译器。而从理论角度上来说,该算法实际上是正则表达式和NFA等价性证明的一部分——事实上,这两种表述形式本质上都对应着相同的语言,即正则语言。

在应用中,算法得到的NFA可以再次通过幂集构造和最小化的过程得到一个对应的最简的确定有限状态自动机(DFA),进而用于匹配正则表达式。但是有些情况下也会直接使用对应的NFA。

算法通过递归地将一个正则表达式划分成构成它的子表达式,在得到每个子表达式对应的NFA之后,根据子表达式之间的运算关系和一系列规则构造表达式自身对应的NFA。具体来说,这套构造规则如下所示 :

对于正则表达式为ε或者只由一个符号构成的情况,则无需继续递归,对应的NFA可以直接由下列规则给出:

空表达式ε直接转化为:

直接转化为:

|可以转化为:

可以直接到达()或()的初态。而()或()原来的终态也可以通过ε转移直接到达整个NFA的新终态。

连接表达式可以转化为:

()的初态成为新的NFA的初态。 原来()的终态成为()的初态。而原来()的终态成为新的NFA的终态。

Kleene*闭包*可以转化为:

()连接起来的ε转移使得可以选择经过或者不经过子表达式。而从()的终态到初态的ε转移使得可以重复任意多次。

相关

  • 中南财经政法大学中南财经政法大学(英语:Zhongnan University of Economics and Law,简称中南大),是中华人民共和国教育部直属的一所以经济学、法学、管理学为主干,兼有文学、史学、哲学、理学、工
  • 新尼德兰新尼德兰(荷兰语:Nieuw-Nederland)是1614年至1674年荷兰在北美洲东部设立的殖民地,其地域大致包括今日美国的纽约州、康乃狄克州、新泽西州和德拉瓦州部分地区。1609年,亨利·哈
  • 远日点拱点(apsis,复数为apsides)是指一个物体的运动轨道的极端点;在天文学中,这个词是指在椭圆轨道上运行的天体最接近或最远离它的引力中心(通常也就是系统的质量中心)的点。最靠近引力
  • 马克·米切尔第二次世界大战马克·安德鲁·"派提"·米切尔(英文:Marc Andrew "Pete" Mitscher,1887年1月26日-1947年2月3日)海军上将, 在第二次世界大战期间担任太平洋战区美军快速航母特遣舰
  • 利莫斯螯虾利莫斯螯虾(学名Orconectes limosus)是蝲蛄科的一种螯虾。它们分布在北美洲东岸,由缅因州至维吉尼亚州詹姆斯河下游,并已引入到欧洲。它们栖息在淤泥的溪,并不像其他螯虾般栖息在
  • 跳跃跳跃是物体的一种运动形式,是指有机体或非生物(如机器人)透过自主推进让自己在空中移动。一些动物、如袋鼠,使用跳跃作为其主要的运动形式。跳跃也是诸多体育项目的关键动作,如跳
  • 汤姆·科尔汤姆·科尔(Tom Cole;1949年4月28日-)是美国的一位政治人物。自2003年开始,他是奥克拉荷马州第4选举区选出的美国众议院议员。在进入国会之前,他曾经担任奥克拉荷马在参议院议员。
  • 约翰·尼利·肯尼迪约翰·尼利·肯尼迪(英语:John Neely Kennedy;1951年11月21日-)是美国路易斯安那州的一位共和党政治家。2016年,他当选为路易斯安那州选出的美国参议院议员。他拥有牛津大学莫德林
  • 球基蘑菇 Peck (1900)蕈伞凸面球基蘑菇(学名:),俗称突然的球根蘑菇(abruptly-bulbous agaricus)或扁球蘑菇(flat-bulb mushroom),是一种担子菌门真菌,隶属于伞菌属。这种真菌可供食用,稍具茴香,
  • 天主教斯普林菲尔德-开普吉拉多教区天主教斯普林菲尔德-开普吉拉多教区(拉丁语:Diocesis Campifontis-Capitis Girardeauensis、英语:Roman Catholic Diocese of Springfield-Cape Girardeau)是美国一个罗马天主教