编译原理2.2 自动机理论

本章将介绍正规文法和有穷自动机之间的关系，所涉及的内容是编译中词法分析技术和自动生成词法分析程序的理论。第3章自动机理论基础1教学要求掌握：正规式，DFA的概念，NFA的概念理解：将DFA转换为NFA，正规文法与有穷自动机间的转换重点：正规式构造DFA，DFA最小化难点：正规表达式构造DFA2一、正规式二、正规文法到正规式三、确定有穷自动机四、不确定有穷自动机五、NFA转换为等价的DFA六、DFA的化简七、正规式和有穷自动机的等价八、正规文法和有穷自动机的等价性*典型例题及解答教学大纲3知识结构词法分析自动构造工具{正规集}正规式有穷自动机（NFADFA)正规文法①⑤⑥②③④4一、正规式和正规集正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。5正规式和正规集的递归定义：对给定的字母表1)

和都是上的正规式，它们所表示的正规集为{}和;2)任何a，a是上的正规式，它所表示的正规集为{a};63)假定e1和e2都是上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i)(e1|e2)为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为(L(e1))*，仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集。7正规式正规集a｛a｝a|b｛a,b}ab｛ab}(a|b)(a|b)｛aa，bb,ab,ba}a*｛，a,aa,…，aa…aa｝(a|b)*｛，a,b,aa,ab,aab,abab,…｝(a|b)*(aa|bb)(a|b)**上所有含有两个相继的a或两个相继的b组成的串例：＝{a,b}，上的正规式和相应的正规集为：8其中的“”读为“或”（也有使用“+”代替

“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”、“”、

“”。连接符“”一般可省略不写。“”、“”和

“”都是左结合的9

讨论下面两个例子例1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式即是字母(字母|数字)

,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的标识符的词法规则.10例2：令＝｛d，，e，＋，－｝，则上的正规式为：d*(.dd*|)(e(+|-|)dd*|)表示的是无符号数。其中d为0～9中的数字。比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。11若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)be1=(ab),e2

=(ab)正规式的等价12对正规式，下列等价成立：e1|e2=e2|e1 交换律e1|(e2|e3)=(e1|e2)|e3 结合律e1(e2e3)=(e1e2)e3 结合律e1(e2|e3)=e1e2|e1e3 分配律(e2|e3)e1=e2e1|e3e1 分配律e=e=e e1e2<>e2e1

S*=(S|ε)*是“连接”的恒等元素（零一律）(a*)*=a*L(e1|e2)=L(e1)

L(e2)=L(e2)

L(e1)=L(e2|e1)13对于任意一个正规文法，存在一个同一语言的正规式。对每一个正规式，存在一个正规文法。即正规式正规文法正规式正规文法文法G=（VN，VT，P，S）令VT=Σ，对正规式r，选择一个非终结符S生成S→r，S为G的开始符号。若x，y都是正规式，对形如A→xy的产生式，写成A→xB，B→y。其中BVN二、正规文法与正规式转换*14对形如A→x*y的产生式，重写为：

A→xBA→yB→xBB→yB为新的非终结符，BVN对形如A→x|y的产生式，重写为：

A→xA→y

不断利用上述规则进行变换即可。15例：将R＝a(a|d)*变换成正规文法。令S是文法开始符号。解：S→a(a|d)*S→aAA→(a|d)*A→(a|d)BA→B→(a|d)BB→

根据上述规则1x＝a，y＝(a|d)*根据上述规则2x＝(a|d)y＝16最后得到：S→aAA→aBA→dBA→B→aBB→dBB→17

正规文法正规式转换规则：

A→xB，B→y正规式为：A=xy

A→xA|y正规式为：A=x*y

A→x，A→y正规式为：A=x|y

例：文法G[S]：S→aAS→aA→aAA→dAA→aA→d转换为正规式18S→aAS→aA→aAA→dAA→aA→dS＝aA|aA＝aA|dAA＝a|dA＝(aA|dA)|(a|d)A＝(a|d)A|(a|d)A＝(a|d)*(a|d)根据上述规则3A→x，A→y推出A=x|y将它化为正规文法变成A→(a|d)A|(a|d)再根据上述规则2转换x＝y＝(a|d)19S＝a(

(a|d)*(a|d))|a=a(a|d)+|a=a((a|d)+|)=a(a|d)+将A代入S＝aA|a得到如下：20

三、确定的有穷自动机DFA有穷自动机(也称有限自动机)作为一种识别装置，是词法分析程序的工具和方法，能自动识别（且是正确识别）正规集。即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。分为确定的有穷自动机（DFA）不确定的有穷自动机（NFA）

21一个确定的有穷自动机M是一个五元组：

M=（Q，Σ，f，q0，Z），其中：①Q是一个有穷集，每个元素表示一个状态；②Σ是一个有穷字母表，每个元素是一个输入字符；③f是转换函数，是在Q×Σ→Q上的映象，如：f(Qi，a)=Qj(Qi,QjQ)；④q0是初态，q0K；⑤ZQ，是终态集。含义：当前状态为Ki，输入字符a，转换为Kj状态DFA映射的唯一性和初态的唯一性22方法如下：初始态用“－”或“”表示；终态点用“＋”或“”表示；若f(Ki

，a)=Kj

，则从状态点Ki

到Kj画弧，标记为a。1、单词的构成规则用状态转换图表示DFA等价表示法：DFA形式定义=状态转换图=状态矩阵23状态转换图(也称状态变迁图)是一张有限方向图。有限个状态，用结点表示状态，其中有一个初态(初态用箭头指出)，至少有一个终态(终态用双圈表示)。状态之间用带箭头的弧线连结，弧线上标记的字符表示在射出状态下可能出现的输入字符或字符类。识别标识符的转换图012字母字母或数字其它*24一个状态图可用于识别一定的字符串，大多数程序设计语言的单词符号都可以用转换图来识别。识别过程是：从初始状态0开始，若读入一个字母，转入1状态，若再读入字母或数字，仍处于1状态，否则转向2状态，结束一个标识符的识别过程。状态上的*表示多读入一个符号。012字母字母或数字其它*25例如：DFAM=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定义如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3状态图如下：0312aaaa状态转换图bbbb26例:一个单部电梯对3层楼进行控制的电梯控制 系统的DFA描述。

问题分析：用户请求（输入）上1、上2、上3

下1、下2、下3

状态设置（所处楼层）

1层2层3层

S1S2S327Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3282、用矩阵表示DFA:方法：行表示状态列表示输入字符元素表示相应状态行和输入字符下的新状态。

“”标明初态，默认第一行是初态。

终态行在表右端标1，非终态标029例如：DFAM=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定义如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3状态转换矩阵30例：－＋baSZa,b表示：f(S,a)=Zf(S,b)=Zf(Z,a)=Zf(Z,b)=ZabSZZZZZ01写成正规式是：(a|b)(a|b)*31Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）电梯控制的状态矩阵表示上1下1上2下2上3下3S1*S1S2*S3*

S1S1 S1S2S2S2 S2

S3 S3S3S3323、DFA接受（识别）的概念：

对于Σ*中的任何字符串t，若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFAM所接受。

若M的初态同时又是终态，则空字可为M所接受。33②

输入字符串t（t表示成Tt1形式，TΣ，t1Σ*），在DFAM上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中QK。4、接受（识别）的理解：①

设QK，函数f(Q,)=Q，则输入字符串是空串，并停留在原状态上。

34例：证明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）=QQ属于终态。得证。bSUVQabba,baa35DFA的确定性表现在：对任何状态s∈S，在读入了输入符号a∈Σ之后，能够唯一地确定下一个状态映射函数δ：S×Σ→S是一个单值函数从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。36③DFAM所能接受的字符串的全体记为L（M）—称为语言（也即句子的集合）结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)文法是语言的生成系统，是从产生的观点来描述语言的。自动机是语言的识别系统，是从识别的观点来描述语言的文法和自动机的对比37四、不确定的有穷自动机NFA一个不确定的有穷自动机NFA

M是一个五元组：M=（Q，Σ，f，q0，Z），其中：①Q是一个有穷集，每个元素表示一个状态；②Σ是一个有穷字母表，每个元素是一个输入字符；③f是一个从Q×(Σ∪ε)到2Q的映象；

④q0是初态，q0Q

；⑤ZQ，是一个终态集。【要点】至少一个初态，若干个终态。38DFA和NFA的主要区别为：（1）DFA任何状态都没有ε转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态；（2）DFA对任何状态S和任何输入符号a，最多只有一条标记为a的边离开S，即转换函数δ：S

ΣS是一个单值部分函数。39例子NFAM=（{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}状态图表示SPZ00,1111∑*上的符号串t被NFAM接受若t∑*，f(S0，t)=P，其中S0∈S，PZ，则称t为NFAM所接受（识别）40Ch2形式语言自动机理论基础2.2自动机基础2.2.2非确定的FA(NFA)例2.24:给出一个接收字符串aa*|bb*的NFAM， 如下图所示。

对字符串aaa的接受路径为0，1，2，2，2，接受 路径中边的标记是ε，a，a，a，它们的连接为字符串aaa，ε在连接中消失。εεabastart04132a41∑*上的符号串t被NFAM接受（识别）:对于Σ*中的任何一个串t，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFAM所识别(读出或接受)。若M的某些结点既是初态结点又是终态结点；或者存在一条从某个初态结点到某个终态结点的道路,其上所有弧的标记均为ε，那么空字ε可为M所接受。42使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该NFA接受。如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA。NFAM所能接受的符号串的全体记为L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。43定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。将NFA转换成接受同样语言的DFA，这种算法称为子集法。NFA与DFA的等价性：对于每个NFAM存在一个DFAM’，使L(M)=L(M’)。NFA可以利用子集法进行确定化，对于一个NFAM总可以构造一个等价的DFAM’。NFA到DFA构造基本思路：DFA的每一个状态对于NFA的一组状态。DFA利用它的一个状态去记录在NFA读入一个输入符号后可能到达的所有状态。五、NFA转换为等价的DFA（NFA确定化）444546-closure(I)=-closure({1})={1，2}=IJ={5，4，3}Ia=-closure(J)=-closure({5，4，3})={5，4，3，6，2，7，8}61a234578aa设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。47把确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:48首先，置第1行第1列为-closure({X})求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合...重复上述过程，知道所有第2，3列子集全部出现在第一列为止。49IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY514236abababab50现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是-closure({X})，它的终态是含有原终态Y的子集。不难看出，这个DFAM与M’等价。51Iab0121322143*344*655*656*340123546aabbbabaababab52Ch2形式语言自动机理论基础2.2自动机基础2.2.3NFA确定化

综述—求Ia步骤：

(1)求ε-closure(I)；

(2)求J；

(3)求ε-closure(J)；NFA确定化关键：(1)消去ε弧；(2)解决映射不唯一问题。ε-closure(I)

求Ia53Ch2形式语言自动机理论基础2.2自动机基础2.2.3NFA确定化例2:有NFAM’如下图所示。12385467aaaεεε

εε54Ch2形式语言自动机理论基础2.2自动机基础2.2.3NFA确定化IIa{2,3,4,5,6,7,8}{3,8}Φ120ε-closure(S0)={1,2}1*2*{2,3,4,5,6,7,8}{3,8}555657六、确定有穷自动机DFA的化简（DFA最小化）说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。将多余状态消除而形成一个最小的等价的DFA。化简不仅是去除死状态，不可能到达状态，还包括状态的合并。

DFA的最小化就是寻求最小状态DFA581、多余状态的概念：所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。如下图中的S4状态是多余的。在图中，没有一个状态能到达S4。当S4是多余时，又可以推出S6是多余的。同样也可以推出S8也是多余的。

最小状态DFA的含义:1.没有多余状态(死状态)2.没有两个状态是互相等价（不可区别）5901S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价602、等价的条件（状态S和T）

两个状态s和t等价：满足一致性——同是终态或同是非终态蔓延性——从S出发读入所有aa和从T出发读入a到达的状态等价。613、等价的方法（分割法）方法：将DFA的状态分割成一些互不相交的子集。把一个DFA（不含多余状态）的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。分割法的核心把DFA的全部状态划分成一些互不相交的子集，使得任何不同的两子集的状态都是可区别的（不等价），而同一子集中的任何两个状态都是等价的.62DFA化简（最小化方法）算法：所有状态分成两个子集——终态集和非终态集；运用判定状态等价的原则分别对两个子集的状态进行分析和划分，若发现某个状态与其它状态不等价，则将其作为一个新的状态子集，如果无法区分，则放在同一子集中；从每个子集中选出一个状态做代表，即可构成简化的DFA；含有原来初态的子集仍为初态，各终态的子集仍为终态。63Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简Step1:形成基本划分。划分为终态集和非终态集。

P0=（{0,1},{2}）考察：{0,1}a={1}⊂{0,1} {0,1}b={2}⊂{2}a例1：设确定有限自动机DFAM'，如图所示。

bbaa021Step2:重新命名。令{0,1}为0，令{2}为1。基本划分

不可对{0,1}再分64Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简baa10化简后的DFAM65CBASaaabbbba,CDBAEFSbaaaaaabbbbbba例2：化简下图的DFA661643257aaaaaaabbbbbbb例3：将下图中的DFAM最小化。67Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简第一步，对M的状态形成基本划分：设p０是基本划分。将p０分成q１,q2，即

p０=({1,2,3,4},{5,6,7})=(q1,q2)第二步，对q１,q2考察知：对p０的q１，I=1时Ia={6} I=2时Ia={7} I=3时Ia={1} I=4时Ia={4}Ib={3} Ib={3} Ib={5} Ib={6}68Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简对q1形成新的划分：

q1=(q3,q4)=（{1,2}，{3,4}） 对p０的q2，I=5时Ia={7}Ib={3} I=6时Ia={4}Ib={1} I=7时Ia={4}Ib={2}

在输入a或b的情况下，q2中的状态{5}与状态{6,7}是不等价的，构成q2新的划分：69Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简q2新的划分：

q2=(q5,q6)=（{5}，{6,7}）由此，对基本划分p0经考察且划分后，形成新的划分p1：

p1=（q3，q4，q5，q6）

=({1,2}，{3,4}，{5}，{6,7})70Ch2形式语言自动机理论基础2.2自动机基础2.2.4DFA的化简

第三步，对新形成的划分p1重复上述第二 步，则对p1中q4的状态{3,4}在输入字符a

的情况下考察其是不等价的，再划分为

q4=（q7,q8）=（{3},{4}）对划分p1经考察且划分后，形成新的划分p2：

p2=（q3,q5,q6,q7,q8）

=({1,2},{5},{6,7},{3},{4})711643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有状态集中的状态皆为等价状态。72合并状态注意：a、由于一个子集中，各状态等价，故只需将原进入该子集中各状态的弧都改为进入所选的状态，子集中各状态射出的弧均改为从该状态射出。b、含有原来初态的子集仍为初态，含原终态的子集仍为终态73例4：将下图中的DFAM最小化。1402357600000000111111741、一个终态（可接受态）组成，一个非终态组成。P0＝({0,1,2,3,5},｛4,6,7})2、{0,1}状态输入1到2状态,{2,5}输入1到4状态,3状态输入1为Φ,2状态和4状态属于不同的子集,P1=({0,1},{2,5},{3})3、{4,7}输入1到状态4,6输入1到Φ,P3=({4,7},{6}){0,1}、{2,5}、{3}、{4,7}、{6}都不可再分了,分别用A,B,C,D,E表示,简化后图如下:751402357600000000111111ADBCE0000011176正规式和FA之间也可以互相转换，转换的方法是从已知的正规式先构造出等价的ε-NFA（本节），去掉ε-NFA中的空动作变换为不含ε迁移的NFA，然后再把NFA转化为DFA，最后再对DFA化简，求得最小DFA。上述各种转换关系可用图2-8表示。七、正规式和有穷自动机的等价性

77正规式和有穷自动机的等价性：

※对于Σ上的NFAM，可以构造一个Σ上的正规式R，使得L(R)=L(M)。※对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L(M)=L(R)。78Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FA(1)增加结点X，并从X引ε弧到达S0中的所有状态；(2)增加结点Y，并从Z中所有状态引ε弧到达Y；step1:将NFAM进行拓广；1、在NFAM上构照正规式R。即从L(M)L(R）方法：在每一条弧上用一个正规式作标记。规则如下：79Y3aXstep2:利用替换规则一逐步消去M’中的结和弧，并用正规式代替原来M’中的弧标记，直至只剩下结为止。XY80(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替换为或(3)321R1R2R331R1R2*R3替换为替换为替换规则一81Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FAY1234bbaa0a,b例1:有NFAM如下图所示。

a,ba,bεε82Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FAY1234bbaa0a,ba,ba,bXεεε83Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FAY123baa,b

4Xεε(a|b)*b(a|b)*a

用规则(3)消去0结和a,b弧

a,b84Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FA用规则(3)消去2,4结和2个a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*85Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FA(a|b)*aa(a|b)*YX用规则(1)消去1,3结

(a|b)*bb(a|b)*86Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FA用规则(2)消去2个弧

(a|b)*bb(a|b)*|(a|b)*aa(a|b)*

YY

X用分配率实施化简

(a|b)*(aa|bb)(a|b)*

X正规式87例2:L(M)如下图：求正规式R，使L(R)=L(M).解：－＋aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)=(a|b)(a|b)*8803412aabba,ba,ba,b例3：M状态图如下：求正规式R，是L(R)=L(M).89解：加x,y结点。a,b03412aabba,ba,bxy90042aabba,ba,bxya,ba,b0aa(a|b)*bb(a|b)*xy91y(a|b)*(aa|bb)(a|b)*x所以L(R)=(a|b)*(aa|bb)(a|b)*

例4：L(M)如下图，求L(R)-++abbaaba,b92解：-++abbaaba,b-abbaaba,bxy93-abbaa|ba,bxy-a|ba|b|abbaxy(a|b|abba)*(a|b)xy所以L(R)=(a|b|abba)*(a|b)=(a|b)*(a|b)=(a|b)+94例5：L(M)如下图，求L(R).-+abbbbabbaa,ba解：-+abbbbabbaa,ba95abba|abb|bb+a,b-aa*(abba|abb|bb)(a|b)*+-所以L(R)=a*(abba|abb|bb)(a|b)*注：abba+abb+bb

不能把bb提取出来962、L(R)NFA，从正规式R构造NFA由正规式V直接形成拓广的FA状态图。构造∑上的NFAM’，使得L(M’)=L(V);方法如下：97Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FAai1)若V是ε或∑上的字符ai,则2)若1）不成立，则V具有V1|V2，V1•V2，(V1)*形式 ，按照替换规则二分解V；3）对新产生的弧标记重复1）、2），直到没有新的弧和结产生为止。得到V相应的M’，且L(M’)=L(v).

XYXYε98Ch2形式语言自动机理论基础2.3正规式与自动机2.3.2正规式与FAR1R1|R2ABR2AB替换为R1*ABεACεB替换为R1ACR2BR1R2AB替换为

R1替换规则二(1)⑵⑶99例1：L(R)=(a|b)*abb，构造NFA使L(N)=L(R)解：xy(a|b)*abbxyabba,bxyabbabxyababb100例：L(R)=(a|b)*(aa|bb)(a|b)*构造L(M)使与L(R)等价。101xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b102xyabaaabbb103八、正规文法和有穷自动机的等价性采用下面的规则可以从正规文法G直接构造一个有穷自动机NFAM；使得L（M）＝L（G）：M的字母表与G的终结符集相同为G中的每个非终结符生成M的一个状态，G的开始符S是开始状态S增加一个新状态Z，作为NFA的终态对G中的形如A→tB的规则（其中t为终结符或ℇ，A和B为非终结符的产生式），构造M的一个转换函数f(A,t)=B对G中形如A→t的产生式，构造M的一个转换函数f(A,t)=Z104

[例2-6]已知正规文法G3＝({S，A，B}，{a，b，c}，P，S)，其中P内包含以下产生式：根据上述转换方法，与G3等价的FAM为：其中δ函数的定义式为：105例2：与文法G［S］等价的NFAM如图4.11G[S]:S→aAS→bBS→ε

A→aBA→bAB→aSB→bAB→ε106有穷自动机转换成等价的正规文法：对转换函数f(A,t)=B,可写一产生式：A→

tB对可接受状态Z，增加一产生式：Z→

ε有穷自动机的初态对应文法开始符有穷自动机的字母表为文法的终结符集107例3：给出与图4.12的NFA等价的正规文法GG＝（｛A，B，C，D｝，｛a，b}，P，A），其中P为：A→aBC→

εA→

bD

D→

aBB→

bC

D→

bDC→

aA

D→

εC→

bD108本章小结