资源描述：
《编译原理分知识点习题 词法分析与有穷自动机》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1.将图1所示的有穷自动机转换成与其等价的正规文法，其中4、5为终止状态。解答：本题考查有穷自动机到正规文法的转换方法。这类题只需要书中所介绍的方法进行即可得到正规文法，本题有穷自动机对应的正规文法G[S]为：A→aB
2、bB
3、cCB→aB
4、bD
5、aE
6、cC
7、b
8、aC→bB
9、cC
10、cE
11、cD→bD
12、bE→aE
13、a12345startabbcbcaacb图1有穷自动机的状态转换图2.给定如图2所示的有穷自动机，试用正规表达式给出它能接受的语言集合。0123aaabbabb图2有穷自动机解：本题考查正规表达式与有穷自
14、动机的等价性。对于一个在输入字母表∑上的FAM，一定可以在字母表∑上构造一个正规表达式e，使得L(e)=L(M).根据状态转换图，从开始状态出发，可以有任意个（包括0个）b作为句子的开始部分；从0状态出发，每输入一个a，不许输入两个b才能到达终止状态后，还可以通过输入a回到状态1，或输入b回到状态0，然后进入递归过程，再输入相同的符号串，所以，该有穷自动机描述的语言为：(b*(aa*b)*b)*3.构造下述正规表达式的DFA。Xy*
15、yx*y
16、xyx解：本题考查由正规表达式构造有穷自动机的方法，本题可按照由正规
17、表达式构造等价的NFA，NFA确定化，DFA最小化3步进行求解。（1）根据题中所给的正规表达式得到相应的DFA如图3所示。ySABFGDEZCxyxxxyyεεεε图3正规表达式Xy*
18、yx*y
19、xyx的DFA。（2）依据该NFA采用子集法构造确定DFA其过程如表1（已换名）所示。表1将NFA确定化为DFA的过程IIxIy[S]0[A,B,F,Z]1[C,D,E]2[A,B,F,Z]1[B,G,Z]3[C,D,E]2[D,E]4[Z]5[B,G,Z]3[Z]5[B,Z]6[D,E]4[D,E]4[Z]5[Z]5
20、[B,Z]6[B,Z]6以所有包含NFA的终止状态Z的DFA状态作为终止状态，得到DFA相应的状态转换图如图4所示02455613xxxxyyyyyy图4DFA的状态转换图（1）对DFA进行最小化，过程如下：已知K={0,1,2,3,4,5,6}。首先将K分成两个子集K1={0,2,3}（非终态集）K2={1,3,4,6}（终态集）在状态集合K1={0,2,3}中，因为{0}x={1}⊂K2{2,4}x={4}⊂K1所以状态0与状态2，4不等价，故K1可分割为K11={0}K12={2,4}在状态集合K12={
21、2，4}中，因为有{2，4}x={4}{2,4}y={5}⊂K2所以，状态2和状态4等价。在状态集合K2={1,3,4,6}中，状态5无输入，状态3有x、y输入，状态1与状态6只有y输入，所以可将K2分割为K21={1,6}K22={3}K23={5}在状态集合K21={1，6}中，状态1输入y到达状态3，状态6输入y到达状态6，所以状态1与6也不等价。进一步将K21分割为K211={1}K212={6}于是，将原状态集合划分为：{0}、{2，4}、{1}、{3}、{5}、{6}。选{2，4}中的2作为代表，原
22、来由状态4导入（出）其余状态的弧改为有状态2导入（出）；然后消去状态4。最后得到最小化后的状态转化图如图5所示。0255613xyyyyyxx图5正规表达式Xy*
23、yx*y
24、xyx的最小化DFA4.构造正规表达式（011）*00相应的DFA。解：本题考查由正规表达式构造确定的有穷自动机的方法。（1）构造正规表达式（011）*00的DFA。按照图3.2所示的转换规则构造正规表达式（011）*00对应的NFA如图6所示。SBCZA0ε10ε0图6正规表达式（011）*00的DFA（2）由正规表达式（011）*00的
25、NFA构造确定的有穷自动机DFA。以NFA的开始状态S的ε闭包ε-CLOSURE（{S}）作为DFA的开始状态，采用子集法将图3.43中所式的NFA确定化，其过程如表2所示。表2将NFA确定化为DFA的过程IIxIy[S，A,B]0[A,B,C]1[A,B]2[A,B,C]1[A,B,C,Z]3[A,B]2[A,B]2[A,B,C]1[A,B]2[A,B,C,Z]3[A,B,C,Z]3[A,B]2以所有包含NFA的终止状态Z的DFA状态作为终止状态，得到DFA相应的状态转换图（以换名）如图7所示。0123011
26、00011图7正规表达式（0
27、1）*00的DFA（1）对该DFA进行最小化。采用够造状态集划分的方法对DFA进行最小化，过程如下：以知K={0，1，2，3}。首先将K分成两个子集K1={0,1,2}（非终态集）K2={3}（终态集）在K1={0,1,2}中，有00=1∈K110=3∈K220=1∈K101=2∈K111=2∈K121=2∈K1
