Thompson构造法

✍ dations ◷ 2025-07-08 17:33:02 #自动机,形式语言,算法

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

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

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

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

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

空表达式ε直接转化为:

直接转化为:

|可以转化为:

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

连接表达式可以转化为:

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

Kleene*闭包*可以转化为:

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

相关

  • 七七节七七节,又名沙夫幼特节、周日节、收获节、新果实节(基督教叫五旬节),是犹太教三大朝圣节日之一,因在逾越节的七周之后举行,故名“七七”。具体日期是在犹太历3月希万月(即西历大约5
  • 国家中医药研究所卫生福利部国家中医药研究所(简称中医所)是中华民国唯一国家级中医药研究公立机构,现隶属于卫生福利部,成立于1963年。掌理有关中医药之研究、实验及发展等事宜,拥有近三十位中药
  • 幂定律幂定律(英语:power law)是一种多项式关系。遵守这关系的多项式,会展现出标度不变性(scale invariance)的性质。最普通的,表达两个变量之间关系的幂定律,其形式为其中,
  • 桂冠诗人桂冠诗人(英语:Poet Laureate)是经由政府官方任命的诗人及其称号。自欧洲中古世纪,在皇帝的侍从队伍内也有诗人,他们的工作就是写下纪念某事或某节庆的诗歌,这种诗人在英国就称之
  • 埃及总统阿拉伯埃及共和国总统是经选举产生的阿拉伯埃及共和国的国家元首。根据埃及宪法的相关规定,总统也是埃及武装力量的总司令和政府行政部门主管,任期四年,可以连任一次。现任总统
  • 日本宪法政治主题《日本国宪法》,又被称为《和平宪法》、《战后宪法》,是日本现行宪法,在1946年11月3日公布、1947年5月3日起施行。该宪法是日本政府在二战战败投降之后的盟军占领时期
  • 应永外寇应永外寇指的是1419年(己亥年,日本应永26年)朝鲜王朝进攻日本对马岛的事件。“应永外寇”日本方面对此战事的称呼,朝鲜则称之为己亥东征、己亥征倭役或者第三次对马岛征伐(제3차
  • 畅销书列表本列表列出了历史上最畅销的单行本和系列书籍。表中所列的为图书的销售量而非印刷量或目前的拥有量。漫画书和教科书不包含在其中。内容主要有关宗教、意识形态等书籍不纳入
  • 阿南迪巴伊·乔希阿南迪巴伊·戈帕尔拉沃·乔希(马拉提语:आनंदीबाई गोपाळराव जोशी,转写:,英国化名 Anandibai Joshee,1865年3月31日-1887年2月26日)是印度最早的女性医生之一。
  • 标准氢电极标准氢电极(英文:Standard Hydrogen Electrode,旧时用Normal Hydrogen Electrode,简称NHE,现已停用),简称SHE,是构成标准电极电势( E