Thompson构造法

✍ dations ◷ 2025-09-18 05:00:34 #自动机,形式语言,算法

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

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

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

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

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

空表达式ε直接转化为:

直接转化为:

|可以转化为:

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

连接表达式可以转化为:

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

Kleene*闭包*可以转化为:

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

相关

  • 建教合作合作教育(英语:Cooperative education,港澳称为合作教育,台湾称为建教合作),是一种结合课堂教学与实际工作经验的结构化教学方法。作为教学过程的一部分,合作教育经验通常被计入学
  • 卢克莱修提图斯·卢克莱修·卡鲁斯(Titus Lucretius Carus,约前99年~约前55年),罗马共和国末期的诗人和哲学家,以哲理长诗《物性论》(De Rerum Natura)著称于世。关于卢克莱修的生平,历史学
  • ClFOsub3/sub高氯酰氟是具有化学式ClFO3的活泼气体,具有类似于汽油和煤油的独特甜味。有毒,是一种强大的氧化剂和氟化剂。是高氯酸的酸性氟化物 。尽管高氯酰氟的生成焓( ΔHf°=-5.2千卡/
  • 海沃德海沃德(Hayward),美国加州城市,属于阿拉米达县,位于费利蒙附近,其名字来自于1851年一名著名的淘金客的名字。该城市在2000年的人口调查中,有140030人。
  • 1992年夏季奥林匹克运动会棒球比赛1992年夏季奥林匹克运动会棒球比赛于7月26日-8月5日在西班牙巴塞罗那举行,首度将棒球项目列为奥运正式比赛项目,共有八个国家的棒球代表队参赛,比赛采预赛单循环赛制,预赛前四强
  • 苏珊娜·阿涅利苏珊娜·阿涅利(意大利语:Susanna Agnelli,1922年4月24日-2009年5月15日)是一名意大利政治家、商人和作家,她也是意大利历史上第一位出任外交部长的女性。苏珊娜·阿涅利出生于意
  • 金容淳金容淳(朝鲜语:김용순,1934年7月5日-2003年10月26日),朝鲜政治家,官至祖国平和统一委员会委员长并负责对南工作,后死于车祸。金容淳出生于平安南道,并在金日成综合大学法学系毕业。19
  • 赤松真人赤松 真人(あかまつ まさと、1982年9月6日 - )、京都府京都市伏见区出身的职业棒球选手外野手。目前效力于中央联盟广岛东洋鲤鱼。2004年选秀会中,被阪神虎第6位指名入团。2008
  • 弗兰克·梅利·斯坦顿弗兰克·梅利·斯坦顿爵士(Sir Frank Merry Stenton,1880年5月17日-1967年9月15日) 是一位研究盎格鲁-撒克逊英格兰的英国历史学家,1937至1945年间任皇家历史学会会长。 是《牛
  • Joy (Red Velvet)朴秀英(朝鲜语:박수영 ,英语:Park Soo Young,1996年9月3日-),艺名Joy(朝鲜语:조이 ,日语:ジョイ),韩国女歌手及演员,为韩国女子团体Red Velvet的领Rapper和副唱。常见译名为朴秀荣及朴首