编译原理第七讲

1、Compiler Construction Principles关于关于有穷自动机我们将讨论如下题目我们将讨论如下题目确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化Compiler Construction Principles1.确定的有穷自动机确定的有穷自动机DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；Compiler Construction PrinciplesDFA定义定义3.f是转换函数，是

2、在KK上的单值映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.Z K是一个终态集，终态也称可接受状态或结束状态。Compiler Construction Principles一个一个DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QCompiler Construction Principles

3、DFA 的状态图表示的状态图表示bSUVQaaaba，bCompiler Construction PrinciplesDFA 的矩阵表示abSUVUQVVUQQQQ字符字符状态状态0001Compiler Construction Principles练习 设（ ， ， ， ，）其中（，），（，）3（，），（，）（，），（，）（，），（，）l构造状态转换图和状态转换矩阵Compiler Construction Principles a b 0 1 2 1 3 2 2 1 3 3 3 3 转移矩阵0132aaaabbbb3状态转换图0 0 0 1Compiler Construction P

4、rinciples例 构造DFA作为一个奇偶校验器，识别0，1组成的含有奇数个1的符号串Compiler Construction PrinciplesDFA M 接受的语言* *上的符号串上的符号串t t被被DFADFA M M接受接受M=（K，f，S，Z）若t *，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集。则称t为DFA M所接受接受（识别识别）.Compiler Construction Principles对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串等于t，则称t可为DFA M所识别(读出或接受)。DFA

5、M所能接受的符号串的全体即NFA M所识别的语言记为 L(M)bSUVQabbabaa,Compiler Construction Principles例例：证明证明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, baaCompiler Construction PrinciplesDFA M所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=

6、L(M)，则称M与M是等价的. 结论： 上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。Compiler Construction PrinciplesDFA的行为很容易用程序来模拟.DFA M=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no)Compiler Construction PrinciplesDFA的确定性表现在1）转换函数f:KK是一个单值函数，也就是说，对任

7、何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。2）初始状态是唯一的Compiler Construction Principles不确定的有穷自动机不确定的有穷自动机NFA定义NFA M=K，f，S，Z，其中K为状态的有穷非空集， 为有穷输入字母表，f为K * 到K的子集（2 K）的一种映射，SK是初始状态集，Z K为终止状态集.Compiler Construction Principles例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，

8、0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，ZCompiler Construction Principles状态图表示SPZ00,1111Compiler Construction Principles矩阵表示矩阵表示矩阵表示01SPS,Z0PZ0ZPP1简化为01SPS,Z0P.Z0ZPP1Compiler Construction Principlesf为为K * 到到K的子集（的子集（2 K）的一种映射）的一种映射具有转移的不确定的有穷自动机 123abcCompiler Construction Principles有如下定理有如下定理: 对任何一个具有

9、转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。与上例等价的一个NFA.2acbb31acacbbCompiler Construction Principles NFA M 所识别的语言所识别的语言 对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。NFA M所能接受的符号串的全体即NFA M所识别的语言记为 L(M)Compiler Construction Principles注意：若M的某些结既是

10、初态结又是终态结， 或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。Compiler Construction Principles DFA是NFA的特例.对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一.Compiler Construction Principles从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的

11、DFA的构造的基本思路是： DFADFA的每一个状态对应的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.Compiler Construction Principles定义对状态集合定义对状态集合I的几个有关运算：的几个有关运算：1. 状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。 状态集合I的任何状态S都属于-closure(I)。2. 状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可

12、从I中的某一状态经过一条a弧而到达的状态的全体。Compiler Construction Principles状态集合状态集合I的有关运算的例子的有关运算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaaCompiler Construction Principles NFA确定化算法确定化算法: 假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的状态

13、集S由K K的一些子集的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，S的状态就是S1 S2；Compiler Construction Principles2 M和N的输入字母表是相同的，即是；3 转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)为M的开始状态；5 St=Si Sk. Se，其中Si

14、 Sk. SeS且Si , Sk,. SeKtCompiler Construction PrinciplesNFA的确定化的确定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621iaaaab

15、bbbCompiler Construction Principles 等价的等价的DFAaCDBAEFSbaaaaabbbbbabFCompiler Construction Principles确定有穷自动机的化简确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 Compiler Construction Prin

16、ciples DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性同是终态或同是非终态传播性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。Compiler Construction Principles C和和D同是终态同是终态,读入读入a到达到达C和和F, C和和F同是终态同是终态, C和和F读入读入a都到达都到达C,读入读入b都到达都到达E. C和和D等价等价aCDBAEFSbaaaaabbbbbabFCompiler Construction Princip

17、les最小状态最小状态DFA对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =（K,f, k0,kt)，,使L(M)=L(M). 结论接受L的最小状态有穷自动机不计同构是唯一的。Compiler Construction Principles“分割法分割法”DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的. 算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.Compiler

18、 Construction Principles DFA的最小化算法的最小化算法 DFA M =（K,f, k0, kt),最小状态DFA M 1.构造状态的一初始划分： 终态kt 和非终态K- kt两组(group) 2.对施用过程过程PPPP 构造新划分new 3. 如new =,则令 final= 并继续步骤4，否则:=new重复2 . 4.为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=rCompiler Construction Principles M 的开始状态是含有S0的那组的代表 M 的终态是

19、含有F的那组的代表 5.去掉M中的死状态.Compiler Construction Principles过程PP : Construction of Construction of newnewFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to state

20、s in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in n e w by the set of all subgroups formed end Compiler Construction Principles DFA的最小化的最小化例子例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaaCompiler Construction Principles二 定义31

21、 一个确定的有限自动机 M（记 作DFA M）是一个五无组 （，0，），其中（）是一个有限状态集合。（）是一个字母表，它的每个元素称 为一个输入符号。（）0，0 称为初始状态。（），称为终结状态集合。（）是一个从 到的单值映射 (，)（,，） 表示当前状态为q,输入符号为a时，自动机将转换到下一个状态，称为的一个后继。Compiler Construction Principles例33 设（， ，）其中（，），（，）3（，），（，）（，），（，）（，），（，）三 一个有三种表示：（1）象上面，用转换函数；（2）转移矩阵；（3）状态转换图。Compiler Construction Princ

22、iplesab012132213333转移矩阵0132aaaabbbb3状态转换图易存储Compiler Construction Principles四 DFA M 接受的语言 如果对所有*，以下述方式递归地扩张的定义 （，），(，）(，w），）， 对任何 ,，则有（）*，若存在， 使（，） 对于例3.3的DFA M和w=baa， (0，ba）=(2,a）= (1,）=3Compiler Construction Principles 从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受。0123aaaabbbbCompiler Cons

23、truction Principles 五. DFA M 判定 ?(）的算法： 输入：$ q:=q0; a:=nextchar; WHILE a$ DO BEGIN q:=move(q,a); a:=nextchar; END; IF q IN F THEN return (”yes) ELSE return (”no);Compiler Construction Principles3.2.2 手工构造识别单词的DFA m 根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFA m。例如：对于Pascal, 标识符：字母开始的字母数字串。 整数：非空数字串。

24、 无符号实数（用表示数字）： （a) dd.d dE(+- ) dd (b) ddE(+- ) dd (c) dd.d dCompiler Construction Principles1342字母字母数字数字数字Pascal 标识符Pascal整数和实数0134652700dddddddEE+7*Compiler Construction Principles3.2.3 编写词法分析程序 根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。 在识别标识符的过程中，要拼写出来，并和保留字区别开来；在识别

25、常数的过程中，要把它转换成机器表示以作为属性值。Compiler Construction Principles 使用下面的全局变量和过程：1. Character 2. Token3. Getchar 4. getbc5. Concatenation6. letter,digit7. Reserve 8. Retract9. buildlist10. returnCompiler Construction Principles作业： 3.2 3.3解释下面每个有限自动机识别的语言是什磨？(a)12345678900000001111111(b)12345aaaaaCompiler Const

26、ruction Principles( c )0120001113.4 给出接受下列在字母表0，1上的语言的DFA: ( a ) 所有以00结束的串的集合； （b) 所有具有三个0的串的集合。0Compiler Construction Principles3. 3 有限自动机 FA m 3. 3. 1 非确定的 有限自动机NFA m 一. NFA m 二. FA 的等价定理 三. 例3.3，用DFA模拟NFA的动作 四. 从一个NFA构造DFA的算法3. 3. 2 确定的 有限自动机的化简 一.何谓确定的 有限自动机的化简 二.等价状态的定义 三.确定的 有限自动机的化简方法Compiler

27、 Construction Principles一. 非确定的有限自动机NFA m定义32 非确定有限自动机是一个五元组 （，q，）其中，q，的意义和的定义一样，而是一个从到的子集的映射，即： 类似FA，NFA m可用状态转换图表示，可定义NFA m接受的语言。Compiler Construction Principles二. FA的等价性定理3 . 1 对任何一个NFA m，都存在一个 DFA m，使L(m)=L(m)证明思想：用m的一个状态对应m的一个状 态集合，用这种方法，能从一个NFA m 构造一个DFA m，称作子集构造法。例3 . 2 NFAm=(0,1 , q0,q1,q0,

28、),其中 (q0,0)= q0,q1, (q0,1)= q1 (q1,0)= (q1,0)= q0,q1Compiler Construction Principlesq0q0q100111q0q0q0q1q0,q10110,1L(m)=L(m)=0,1+100,1*Compiler Construction Principles014236578910aabbb012470,1,2，4,7a3a8612473,8,6,1,2,4,7b5b961247a5,9,6,1,2,4,7bb56124b105,10,6,1,2,4,77b例3.3从具体例子的讨论,提炼出从NFA构造DFA的算法。Com

29、piler Construction Principles四. 从NFA构造DFA的算法 1.closure(S) 的定义和算法 从S中任一状态出发，仅沿弧到达的状态集合，T=S ( edge(t, ), 其中，edge(t, a)是NFA中从状态t出发，仅沿a弧到达的状态集合。如下计算T： T:=S; REPEAT T:=T ; T:=T ( edge(t, ) (tT) UNTIL T=TtTCompiler Construction Principles2. DFA的转移函数 DFAedge(d, a)= closure( edge(t, a)其中， d是NFA的状态集， a 。 从NF

30、A构造DFA，是对于NFA的所有输入,，用DFA模拟NFA的动作，令t1是NFA的初态，DFA的初态d1= closure(t1) ，若， dj= DFAedge(di, a),那磨，从di到dj存在一条用a标识的弧。算法3,2 从一个NFA构造一个DFAtdCompiler Construction PrinciplesStates1 :=-closure(t1); p:=1; j:=1;WHILE j=p DO for each a e:=DFAedge(statesj,a); IF e=statesi for some i=p THENtransj,a=i ELSE p: =p+1; s

31、tatesp:=e; transj,a:=p; ; ; j:=j+1; Compiler Construction Principles01436578910abbb2astatesab3,8,6,1,2,4,70,1,2,4,725,6,1,2,4,7325,9,6,1,2,4,742325,10,6,1,2,4,7523Compiler Construction Principles3.3.2 确定的有限自动机的化简一. 何谓确定的有限自动机的化简 所谓一个DFA m=(, Q, q0, F, )的化简是指寻找一个状态数比较少的DFA m,使L(m)=L(m)。而且可以证明， 存在一个最

32、少状态的DFA m, 使L(m)=L(m)。二.等价状态的定义 设p,q Q ，若对任何w * , (p,w) F 当且仅当 (q,w) F ，则称p和q是等价状态。否则，称p和q是可区别的。Compiler Construction Principlesq1q2q3q4q1q2q3q6q4q5q7baaaaaaaaaaabbb,bbbbbbbCompiler Construction Principles1.等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类；2 .两个状态p和q等价应满足如下条件：（a）一致性条件， p和q必须同时或为接受 状态或为非接受状态；（b）蔓延性条

33、件，对于a ， （p,a)=r, （q,a)=s, r和s必须等价; 相反, r和s不等价, p和q不等价。 判定两个状态p和q不等价，只要o找到一个w*， 使（p,w)F 且（q,w) F，或者相反。 W称为判别序列。Compiler Construction Principles三. 方法： 构造一张表，对每一个状态对（qi,qj）（ij）有一表项，每当发现一对状态不等价时，就放一个x到相应表项中。1 . 根据一致性条件，在每一个对应于终结状态和非终结状态的表项中放上一个x。2 .根据蔓延性性条件，对每一个状态对（p,q），若a，（p,a）=r， （q,a）=s，r和s不等价，则（p,q）

34、不等价。重复2，直到没有新的不等价状态对出现。Compiler Construction Principlesq8q7q6q5q1q2q311110111000000 xxxxxxq2q3q5q6q7q8q1 q2 q3 q5 q6 q7xxxxxxxxxxxxxCompiler Construction Principles3.4 正规表达式 用正规表达式描述单词，把它转换成识别装置-有限自动机。3.4 .1正规表达式与单词 一.正规表达式的定义 二.正规表达式的代数性质 三.正规定义式 四.例示，用正规定义式描述单词3.4 .2 正规表达式与有限自动机的等价性 L( r )=L(m)Com

35、piler Construction Principles3.4.2 正规表达式与有限自动机的等价性 单词结构用正规表达式描述，用机械的方法（程序），把正规表达式变换成等价的有限自动机。定理3.2 设r是上一个正规表达式，则存在一个FA m接受L( r )。反之亦然。证 对正规表达式r的运算数目作归纳。设r具有零个运算，则或r=或r= 或r=a q0q0q1q0q1ar=r= r=aCompiler Construction Principles设结论对少于i(i1)个运算的正规表达式r成立。当r有i个运算时，有三种情况： 情况1 r=r1r2 情况2 r=r1r2 情况3 r=r1* 有 m

36、1=(1,Q1,q1,F!,1), m2=(2,Q2,q2,F2,2) 且L(m1)=L( r 1), L(m2)=L(r2) ，由m1和m2构造m,使得 L(m)=L( r ).构造方法图示如下：q0q1f1f2q2f0m2m1r=r1r2Compiler Construction Principlesq0q1f1q2f0m2m1f2q1f1r=r1r2r=r1* 上述证明方法，是对于一个正规表达式r,构造一个FA m,且L(m)=L( r )的算法,但假定知道r的计算顺序。 正规表达式r的语法是上下文无关文法。Compiler Construction Principles例3.5构造与下

37、列正规式 ( c) r=01*1 等价的有限自动机。语法树如左下图。*011q0q10q2q31q2q3q5q41Compiler Construction Principles01q0q1q6q71q2q5q4q0q1q4q2q3q3q6q7110q8q5q9Compiler Construction Principles 对于上任一NFA m，能构造上一个正规表达式r，使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进x,y两个结。从x用弧连接到m的所有初态结点，从m的所有接受态结点用弧连接到y，从而构成一个新的NFA m，L(m)=L

38、(m)。下面，逐步消去NFA m中的状态结点，直至剩下x,y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则。Compiler Construction Principlesabcacacacabcacr1r2r2r2r1r1r3r1r2r1r2r1r2*r3替换规则代之以代之以代之以Compiler Construction Principles3.5 正规文法与有限自动机(FA)的等价性 L(G)=L(m)定理3.3 对于每一个右线性正规文法或左 线性正规文法G，都存在一个FA m，使 L(m)=L(G)证 给定右线性正规文法G=(VT,VN,S,P

39、),设f VN ，令m=(VT ,Q, S, F, ), 其中，F= fQ= VNf, 转移函数 定义如下： (a) Aa, (A,a)=f (b) A aA1aA2 . aAn (A,a)= A1,A2 ,. ,An Compiler Construction Principles 给定左线性正规文法G=(VT, VN, S, P), 设q0VN ，令m=(VT ,Q, q0 ,S , ), 其中，Q= VN q0 , 转移函数 定义如下： (a) Aa, (q0,a)=A (b) A1 A,a, A2Aa , An Aa (A,a)= A1, A2 ,. , A n定理3.4 对于每一个D

40、FA m，都存在一个右 线性正规文法G和一个左线性正规文法G， 使L(m)=L(G)=L(G)。证 设m=(, VN , S,F, ),右线性正规文法G的构造方法如下：Compiler Construction Principles若sF, G=(,V N ,S,P), P的定义如下：对任何a 及A,B VN, 若有(A,a)=B, 则 (a) B F, A aB (b) B F A aaB若s F, S0 V N , S0 S 构造左线性正规文法， P的定义如下：对任何a 及A1,A2 VN, 有(A1,a)=A2, 则 (a) A1是初态， A2 a (b) A1不是初态, A2 A1aC

41、ompiler Construction Principles例3.6 DFA m 右线性正规文法G NFA m左线性正规文法G ADCB0,1111000A00B 1DB 0D 1CC 0 0B 1DD 0D 1DCompiler Construction PrinciplesADCB0,1111000S0C0B 0C0C B 1D 1B0 C1 D0 D1f00NFA m左线性正规文法Compiler Construction Principles3.6词法分析程序的自动构造工具LEX简介一.原理 单词的结构用正规式描述 正规式 NFA DFA min DFA二.用LEX建立词法分析程序的

42、过程LEX编译器LEX源程序lex.1Lex.yy.cCompiler Construction PrinciplesC编译器Lex.yy.ca.outa.out输入流单词序列三.lex源程序 lex源程序由三部分组成Compiler Construction Principles声明%翻译规则%辅助过程声明包括变量，显明常量和正规定义式。 翻译规则的形式为： p1 动作1 p2 动作2 p n 动作nCompiler Construction Principles 每个pi是正规定义式的名子，每个动作i是正规定义式pi识别某类单词时，词法分析器应执行动作的程序段。用C书写。 辅助过程是动作需

43、要的，这些过程用C书写，可以分别编译。 词法分析器返回给语法分析器一个单词, ,把单词的属性值存放于全程变量yylval中。Compiler Construction Principles3.5 对于下列各语言，分别写出它们的正规 表达式： (a) 字母表a,b,c上的串，其中第一个a先于 第一个b。 (b) 具有偶数个a的字母表a,b,c上的串。 ( c ) 0，1上的串，该串看成二进制是4的 倍 数。 (d) 0，1上不含子串011的串。 (e) 0，1 上的串，有偶数个0和奇数个1。 (f) 英文字母组成的所有符号串，且顺序 包 含五个元音字母。Compiler Construction Principles3.7 构造等价于下列正规表达式的NFA (a) ab|(a|bb)a*b (b) (a|b)*|(bb)*Compiler Construction Principles识别识别Pl0单词的单词的FACompiler Construction PrinciplesNFA的确定化的确定化 More exampleCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompile