正则表达式自动机构造法_Thompson方法的改进_文库下载
1亿文档 免费下载
当前位置： &
& 正则表达式自动机构造法_Thompson方法的改进
正则表达式自动机构造法_Thompson方法的改进
正则表达式自动机构造法(NFA)_Thompson方法的改进
福建电脑２００６年第８期
由正规式构造ＦＡ＿＿＿＿Ｔｈｏｍｐｓｏｎ方法的改进
段文秀，王付山，于学斗
（德州学院计算机系山东德州２５３０２３）
要】：本文对由正规表达式改造为有限自动机的方法－－Ｔｈｏｍｐｓｏｎ方法存在的问题进行了分析，并在此基础上，对
边，提高了编译程序的工作效率。Ｔｈｏｍｐｓｏｎ方法进行了改造，大大地减少了有限自动机的状态数和ε
：编译程序正规表达式有限自动机Ｔｈｏｍｐｓｏｎ方法【关键字】
有限自动机（ＦｉｎｉｔｅＡｕｔｏｍａｔａ，简称为ＦＡ）在编译程序中用
来识别某些字符串是否符合某种词法规则，也即用来判定某字符串是否是某一程序设计语言的一个单词。正规表达式（Ｒｅｇｕ－ｌａｒＥｘｐｒｅｓｓｉｏｎｓ）在编译程序中用来描述程序设计语言中某种单词的词法结构
。二者在编译程序中的作用如下图所示：
Ｍ＝（Ｋ１∪Ｋ２∪｛Ｓ０，Ｓｆ｝，∑１∪∑２，ｆ，Ｓ０，｛Ｓｆ｝）其中，映射ｆ定义为：
ｆ（Ｓ０，ε）＝｛Ｓ１０，Ｓ２０｝
因此，将正规式改造为等价的ＮＦＡ是编译程序中的重要过
程。Ｔｈｏｍｐｓｏｎ方法是一种有效的改造方法，但是这种方法改造的不确定的有限自动机（ＮｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃＦｉｎｉｔｅＡｕｔｏｍａｔａ，简称
边，会给后续的自动机确定化和最小ＮＦＡ）有太多的状态数和ε
化工作带来极大的不便。
正规式ｒ＝ａ（ｂ｜ａａ）＊ｂ使用Ｔｈｏｍｐｓｏｎ方法构造的ＮＦＡＭ对应的状态转换图为：
此ＮＦＡ共有１４个状态，１１条ε边。后续的确定化工作会耗费大量的时间和空间，所以我们有必要对Ｔｈｏｍｐｓｏｎ方法进行改进，以期得到的ＦＡ有尽可能少的状态数和尽可能少的ε边，更大程度的提高词法分析程序的工作效率。１．Ｔｈｏｍｐｓｏｎ方法简介
Ｔｈｏｍｐｓｏｎ方法根据正规式ｒ的定义，对ｒ所含运算符的个数ｎ递归的给出，由此算法构造的ＦＡ是一个含有ε动作的ＮＦＡ，其中只有一个初态和一个终态，而终态不再有任何射出矢线。线。
，或者字母表∑中的单个字符ａ。１）．ｎ＝０时，ｒ必然为Φ，ε１）．ｎ＝０时，算法同前。
显然，在此情况下，相应的ＮＦＡ对应的状态转换图分别为下图２）．设ｎ＝１，２，…，ｋ－１时，ｒ相应的ＤＦＡ均能做出，则当ｎ＝ｋ
时，根据正规式的定义，ｒ不外是ｒ１｜ｒ２，ｒ１＊ｒ２和ｒ１＊这三种形式之（ａ），（ｂ），（ｃ）：
一，其中ｒ１和ｒ２均为正规式，且它们所含运算符的个数均不会超过ｋ－１，故可假定相应于ｒ１和ｒ２的确定有限自动机Ｍ１＝（Ｋ１，∑１，ｆ１，Ｓ１０，Ｓｆ１）及Ｍ２＝（Ｋ２，∑２，ｆ２，Ｓ２０，Ｓｆ２）均已作出，就上述三种形式分别给出构造相应于ｒ的ＤＦＡ方法。ｒ＝Φｒ＝εｒ＝ａ
（ａ）（ｂ）（ｃ）①．ｒ＝ｒ１｜ｒ２的情况。
将Ｍ１的初态Ｓ１０和Ｍ２的初态Ｓ２０合并为一个初态Ｓ０，原来２）．设ｎ＝１，２，…，ｋ－１时，ｒ相应的ＮＦＡ均能做出，则当ｎ＝ｋ
时，根据正规式的定义，ｒ不外是ｒ１｜ｒ２，ｒ１＊ｒ２和ｒ１＊这三种形式之由Ｓ１０或Ｓ２０射出的矢线改由Ｓ０射出，射入Ｓ１０或Ｓ２０的矢线改为一，其中ｒ１和ｒ２均为正规式，且它们所含运算符的个数均不会超射入Ｓ０。将Ｓｆ１和Ｓｆ２合并为一个终态Ｓｆ，原来射入Ｓｆ１或Ｓｆ２的矢过ｋ－１，故可假定相应于ｒ１和ｒ２的非确定有限自动机Ｍ１＝（Ｋ１，∑线改为射入Ｓｆ，由Ｓｆ１或Ｓｆ２射出的矢线改由Ｓｆ射出。即所构造的
ＮＦＡ为１，ｆ１，Ｓ１０，Ｓｆ１）及Ｍ２＝（Ｋ２，∑２，ｆ２，Ｓ２０，Ｓｆ２）均已作出，就上述三种形式分别给
出构造相应于ｒ的ＮＦＡ方法。
①．ｒ＝ｒ１｜ｒ２的情况。Ｍ＝（Ｋ１∪Ｋ２∪｛Ｓ０，Ｓｆ｝－｛Ｓｆ１，Ｓｆ２，Ｓ１０，Ｓ２０｝，∑１∪∑２，ｆ，Ｓ０，｛Ｓｆ｝）引入两个新的状态Ｓ０和Ｓｆ分别作为Ｍ的初态和终态，并其中，映射ｆ定义为：按下图方式用ε矢线将Ｍ１和Ｍ２并联起来，即所构造的ＮＦＡ将ｆ１中所有的Ｓ１０替换为Ｓ０，将所有的Ｓｆ１替换为Ｓｆ；为将ｆ２中所有的Ｓ２０替换为Ｓ０，将所有的Ｓｆ２替换为Ｓｆ；
）＝ｆ（，Ｓｆ２，ε）＝｛Ｓｆ｝ｆ（，Ｓｆ１，ε
②．ｒ＝ｒ１＊ｒ２的情况。
此时，用Ｍ１的初态作为Ｍ的初态，用Ｍ２的终态作为Ｍ的终态，并用ε矢线按下图的方式将Ｍ１和Ｍ２串联起来，即所构造的ＮＦＡ为：
Ｍ＝（Ｋ１∪Ｋ２，∑１∪∑２，ｆ，Ｓ１０，｛Ｓｆ２｝）其中，映射ｆ定义为：
ｆ（Ｓ，ａ）＝ｆ１（Ｓ，ａ）当Ｓ∈Ｋ１－｛Ｓｆ１｝，且ａ∈∑１∪｛ε｝ｆ（，Ｓｆ１，ε）＝｛Ｓ２０｝
ｆ（Ｓ，ａ）＝ｆ２（Ｓ，ａ）当Ｓ∈Ｋ２，且ａ∈∑２∪｛ε｝时③．ｒ＝ｒ１＊的情况
此时，引入两个新的状态Ｓ０和Ｓｆ，并按下图的方式来构造ＮＦＡ，即所构造的ＮＦＡ为：
Ｍ＝（Ｋ１∪｛Ｓ０，Ｓｆ｝，∑１，ｆ，Ｓ０，｛Ｓｆ｝）其中ｆ定义为：
ｆ（，Ｓ０，ε）＝｛Ｓ１０，Ｓｆ｝
｝时ｆ（Ｓ，ａ）＝ｆ１（Ｓ，ａ）当Ｓ∈Ｋ１－｛Ｓｆ１｝，且ａ∈∑１∪｛ε
ｆ（Ｓｆ１，ε）＝｛Ｓ１０Ｓｆ｝
２．改造的Ｔｈｏｍｐｓｏｎ方法
根据正规式间的等价关系将ｒｓ｜ｒｔ改写为ｒ（ｓ｜ｔ）的形式，将ｓｒ｜ｔｒ改写为（ｓ｜ｔ）ｒ的形式。根据正规式的定义，对正规式所含运算符的个数ｎ递归的给出，由此算法构造的ＦＡ是一个不含有ε动作的ＮＦＡ，其中只有一个初态和一个终态，而终态可有射出矢
（下转第８３页）
Word文档免费下载：（下载1-2页，共2页）
一种改进的有限自动机正则化方法研究_专业资料。有限自动机与正则表达式具有等价性,针对传统算法在处理特定有限自动机正则化中的缺陷,通过对终止状态F,加入δ(F,ξ...构造正则表达式的Follow自动机并行算法研究_专业资料。给出了一种从正则表达式到Follow自动机的并行化算法.先构造正则表达式的Thompson自动机,再对其消除ξ边,实现Thomp...由正规式构造等价的NFA M的方法 (Thompson构造法): (1) 将正规式R表示为拓...正则表达式和有限自动机 14页 免费 编译原理(2)词法_1(正规... 38页 免费...形式语言与自动机 6 正则表达式_电脑基础知识_IT/...用正则表达式描述出来,自动系统能够生成词 法分析程序...在正则运算 下的封闭性的证明中给出的构造证明方法...构造 NFA: 使用 Thompson 构造法 : 输入: 字母表 ∑ 上的一个正规表达式 r...自动机是正则表达式的另一种形式, 自动机可以应用到二次平台的开发, 工业控制...构造正则表达式的最佳NFA算法的选择_专业资料。介绍了工程中广泛应用的四种经典和先进的不确定有限自动机NFA的基本构造方法,它们是位置自动机Apos邮部分派生自动机Apd,...本文对由正规表达式改造为有限自动机的方法――Thompson方法存在的问题进行了分析,...构造F A Topo法的 改进 hmsn方 段文秀, 王付 山, 于学斗 (州学 院计 ...构造等价的正则表达式(状态消去法) 思路: (1) 扩展自动机的概念,允许正则...BUPT 18 右线性文法=& 有限自动机(续)证明方法:通过两者定义的语言中任意一个...( A ) A Lex 是一个词法分析器的生成器 B ...能被确定的有穷自动机识别,但不能用正则表达式表示...分析程序的结构 40. 若一个文法是递归的,则它所...一种基于智能有限自动机的正则表达式匹配算法_张大方_机械/仪表_工程科技_专业...正则表 达式的 DFA 构建过 程: 首先采用 Thompson 构造法[ 6] 将正 则表...3.3 有穷自动机　
&&&有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。
&&&有穷自动机分为两类：
&&&&&&确定的有穷自动机和不确定的有穷自动机
&&&关于有穷自动机我们将讨论如下问题
&&&&&&确定的有穷自动机DFA
&&&&&&不确定的有穷自动机NFA
&&&&&&NFA的确定化
&&&&&&DFA的最小化
1.确定的有穷自动机
1.DFA定义：
一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中
1.K是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表
3. f是转换函数，是在K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
4. S∈K是唯一的一个初态；
DFA&&&M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：
&&&f（S，a）=U&&&&&&f（V，a）=U
&&&f（S，b）=V&&&&&&f（V，b）=Q
&&&f（U，a）=Q&&&&&&f（Q，a）=Q
&&&f（U，b）=V&&&&&&f（Q，b）=Q
3.DFA状态图表示
假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=&”或标以“-”，终态结点用双圈表示或标以“+”，若 f(ki
,a)=kj，则从状态结点ki到状结点kj画标记为a的弧；
4.DFA矩阵表示
一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=&”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。
5.DFA所接受
将转换函数进行扩充
一个输入符号串t，（将它表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在DFA&&M=（K，Σ，f，S，Z）上运行的定义为：f（Q， Tt1）=f（f（Q，T），t1）其中Q∈K
例：证明t=baab被下图的DFA所接受。
&&&f（S，baab）=f（f（S，b），aab）
&&&=f（V，aab）= f（f（V，a），ab）
&&&=f（U，ab）=f（f（U，a），b）
&&&=f（Q，b）=Q
Q属于终态。
while c&&eof
{ K:=f(K,c);
if K is in Z then
return (“yes”);
else return (“no”);
6.DFA的确定性
DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。
DFA的行为很容易用程序来模拟.
DFA M=（K，Σ，f，S，Z）的行为的模拟程序
{K:=f(K,c);
in Z then return (‘yes’)
else return (‘no’)
2.不确定的有穷自动机（NFA）
NFA M=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）
f（S，0）={P}
f（Z，0）={P}
f（P，1）={Z}
f（Z，1）={P}
f（S，1）={S，Z}
4.矩阵表示
∑*上的符号串t被NFA M接受也可以这样理解
对于Σ~中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为ε，那么空字可为M所接受。
6.DFA是NFA的特例.对每个NFA 　N一定存在一个DFA　Ｍ ，使得? L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。
有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法.
与某一NFA等价的DFA不唯一.
NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态

3.NFA转换成DFA
1.定义对状态集合I的几个有关运算
1.? 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。
2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。
2.状态集合I的有关运算的例子
I={1}, e-closure(I)={1,2}；
I={5}, e-closure(I)={5,6,2}；
move({1,2},a)={5,3,4}
e-closure({5,3,4})={2,3,4,5,6,7,8}；
3.NFA确定化算法:
1. M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的元素，其中S1,
S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]；
2、M和N的输入字母表是相同的，即是?；
3、转换函数是这样定义的d([S1 S2,... Sj],a)= [R1R2... Rt]其中
{R1,R2,... , Rt} = e-closure(move({S1,
S2,,... Sj},a))
4、S0=e-closure(K0)为M的开始状态；
例：P55 图4.4的NFA＝&DFA
4.构造NFA? N的状态K的子集的算法：
1.开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。
2.while （C中存在尚未被标记的子集T）do
{ 标记T； for 每个输入字母a&&&do
{ U:= e-closure(move(T,a));
if&&& U不在C中&&&then 将U作为未标记的子集加在C中
5.例：NFA的确定化
6.等价的DFA
4.确定有穷自动机的化简
`1.确定有穷自动机的化简
寻找一个状态数最少DFA M’,使得L(M)=L(M’)
说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。
2．DFA的最小化就是寻求最小状态DFA
最小状态DFA的含义:
没有多余状态(死状态)
没有两个状态是互相等价（不可区别）
两个状态s和t等价的条件：
兼容性（一致性）条件――同是终态或同是非终态
传播性（蔓延性）条件――从s出发读入某个a(a)??和从t出发读入某个a到达的状态等价。
C和D同是终态,读入a到达C和F,
C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价
3.最小状态DFA
对于一个DFA M =（K,∑,f, k0,,kt)，存在一个最小状态DFA? M’ =（K’,∑,f’,
k0’,,kt’)，,使L(M’)=L(M).
接受L的最小状态有穷自动机不计同构是唯一的。
“分割法”
DFA的最小化算法的核心
把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.最后每个子集中选出一个代表，同时消除其他等价状态。
4.DFA的最小化―例子
１．将Ｍ的状态分为两个子集一个由终态｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态｛Ｓ，Ａ，Ｂ｝组成：
２．考察｛Ｓ，Ａ，Ｂ｝是否可分．
因为Ａ属天｛Ｓ，Ａ，Ｂ｝而Ｃ属天｛Ｃ，Ｄ，Ｅ，Ｆ｝是两个不等价状态，所以可分为｛Ａ｝和｛Ｓ，Ｂ｝两个集合．
３．考察｛Ｓ，Ｂ｝是否可再分：
因为Ｂ属天｛Ｓ，Ｂ｝，Ｄ属于｛Ｃ，Ｄ，Ｅ，Ｆ｝所以，可再分为｛Ｓ｝和｛Ｂ｝两个集合．
４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：
因为Ｃ，Ｄ，Ｅ，Ｆ输入a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝所以不可再分：
５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝来代替则最小化的ＤＦＡ如图：2002年7月 PHP大版内专家分月排行榜第一2002年5月 PHP大版内专家分月排行榜第一2002年7月 C/C++大版内专家分月排行榜第一
2003年1月 PHP大版内专家分月排行榜第三2002年7月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。>> 该C++源码为正规式到有穷自动机的转化过程的实现
该C++源码为正规式到有穷自动机的转化过程的实现
所属分类：
下载地址：
zhenguishidaoyouqion文件大小：13.81 kB
分享有礼！ 》
请点击右侧的分享按钮，把本代码分享到各社交媒体。
通过您的分享链接访问Codeforge，每来2个新的IP，您将获得0.1 积分的奖励。
通过您的分享链接，每成功注册一个用户，该用户在Codeforge上所获得的每1个积分，您都将获得0.2 积分的分成奖励。
该C++源码为正规式到有穷自动机的转化过程的实现-C source code for the formal ceremony to DFA's transformation process to achieve
Sponsored links
源码文件列表
温馨提示： 点击源码文件名可预览文件内容哦 ^_^
&Comment:&0.00 B
&Name&0.00 BDate Time
（提交有效评论获得积分）
评论内容不能少于15个字，不要超出160个字。
njust代码很实用，而且算法也不错哦!
里面的注释 很好
评价成功，多谢！
下载zhenguishidaoyouqion
CodeForge积分（原CF币）全新升级，功能更强大，使用更便捷，不仅可以用来下载海量源代码马上还可兑换精美小礼品了
您的积分不足，优惠套餐快速获取 30 积分
10积分 / ￥100
30积分 / ￥200原价 ￥300 元
100积分 / ￥500原价 ￥1000 元
订单支付完成后，积分将自动加入到您的账号。以下是优惠期的人民币价格，优惠期过后将恢复美元价格。
支付宝支付宝付款
微信钱包微信付款
更多付款方式：、
您本次下载所消耗的积分将转交上传作者。
同一源码，30天内重复下载，只扣除一次积分。
鲁ICP备号-3 runtime:Elapsed:167.860ms - init:0.1;find:0.6;t:0.4;tags:0.7;related:131.1;comment:2.1; 27.69
登录 CodeForge
还没有CodeForge账号？
Switch to the English version?
^_^"呃 ...
Sorry!这位大神很神秘，未开通博客呢，请浏览一下其他的吧不确定的有限自动机
NondeterministicFiniteAutomata NFA
编译原理基础-计算机理论-百易书市 2 正规式与正视集
2.2.3 记号的说明
2.3 记号的识别——有限自动机
2.3.1 不确定的有限自动机（NondeterministicFiniteAutomata，NFA）
2.3.2 确定的有限自动机（DeterministicFiniteAutomata，DFA）
基于3个网页-
nondeterministic finite automaton
不确定的有限自动机
基于3个网页-
首先，证明了半环上的有限自动机与不确定的有限状态自动机识别语言的一致性。
To begin with, the identity will be proved between the finite automaton based on semirings and non-deterministic finite automaton.
针对上述建模方式，本文利用扩展有限状态自动机（EFSM）来检测入侵，DEFSM是我们设计的一种不确定的扩展有限状态机。
To cooperate with such modeling, we use the Extented Finite State Machine(EFSM) to detect the invasion, and the DEFSM is a sort of EFSM that we defined.
$firstVoiceSent
- 来自原声例句
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！