Thompson构造法

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

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

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

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

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

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

空表达式ε直接转化为:

直接转化为:

|可以转化为:

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

连接表达式可以转化为:

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

Kleene*闭包*可以转化为:

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

相关

  • 彼得·塞曼彼得·塞曼(荷兰语:Pieter Zeeman,荷兰语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000
  • 作业风险作业风险是指所有因内部作业、人员及系统之不当与失误,或其他外部作业与相关事件,所造成损失之风险,其中包括“法律风险”,但排除策略风险及声誉风险。尤其近年来在银行界通过新
  • 接吻病传染性单核白血球增多症(英语:Infectious mononucleosis,缩写“IM”,别名mono、glandular fever、Pfeiffer's disease、Filatov's disease)是一种由EB病毒造成的传染病。大部分人
  • 欧洲南天文台欧洲南方天文台(英语:The European Southern Observatory,縮寫:ESO)是为在南半球研究天文学,在政府间组织的一个研究机构,由15个国家组成和支援的一个天文研究组织。它成立于1962年
  • 荷兰10万人口以上城市列表以下是荷兰10万人口以上城市列表
  • 埃克曼螺旋埃克曼螺旋(英语:Ekman spiral),或称为埃克曼螺线,是指海洋表面附近的海流因为风和科氏力的作用造成海流方向旋转的结构。这个结构以瑞典海洋学家沃恩·华费特·埃克曼命名。表面
  • 急救员紧急医疗技术员(英语:Emergency medical technician,缩写为EMT)或救护技术员(英语:Ambulance technician),简称救护员、急救员,指提供紧急医疗服务的专业人员,但在一些国家,亦被借用来
  • Rockstar TorontoRockstar Toronto(前身为Rockstar Canada)是一个Rockstar Games旗下的电子游戏开发公司。该公司于1994年成立,最初名称为Alternative Reality Technologies,隶属于GameTek旗下的
  • 2010年中国足球超级联赛2010年中国足球协会超级联赛(由于赞助原因,亦被冠名为2010倍耐力中超联赛)是自2004年中国足球超级联赛创立以来,由中国足球协会主办的第7届中超联赛,也是自1994年中国足球职业化
  • 疣海胆疣海胆(学名:),又名瘤海胆,是一属已灭绝的海胆。它们生存于白垩纪至始新世,分布在亚洲、欧洲及北美。它们的介壳为扁圆形。顶盘和嘴周围的膜所占据的部分很宽阔。步带与步带区间的