第三章 词法分析作业答案.ppt

1.求正则式（a|b)(a|b|0|1)*对应的正则文法（右线性文法），画状态转换图。解:(a|b):S a|b(a|b|0|1)*:A aA|bA|0A|1A合并合并:S a|b A aA|bA|0A|1A|SABZa,b,0,1ab2、求正则文法GZ：Z 0Z|1Z|0A A 0B B 0 对应的正则式:解:(0|1)*0002.已知有限自动机如图(1)(1)以上状态转换图表示的语言有什么特征？以上状态转换图表示的语言有什么特征？(2)(2)写出其正规式与正规文法写出其正规式与正规文法.(3)(3)构造识别该语言的有限自动机构造识别该语言的有限自动机DFA.DFA.解：解：（1）L=W|W 0,1,并且并且W至少有两至少有两个连续的个连续的1（2）正则式为正则式为（0|1)*11(0|1)*正则文法正则文法G(Z)为：为：Z0Z|1Z|1A A 1B|1 B 0B|1B|0|1（3）将图中有限自动机确定化：将图中有限自动机确定化：首先从处态首先从处态A出发：出发：I I0 I1(1)A (1)A (2)A,B(2)A,B (1)A (3)A,B,C(3)A,B,C (4)A,C (3)A,B,C(4)A,C (4)A,C (3)A,B,C其相应的DFA如下图：将将这个这个DFA最小化：最小化：首先分终态和非终态两个集首先分终态和非终态两个集K1=1,2 和和 K2=3,4 由于状态由于状态1输入输入1到达状态到达状态K1集，而状态集，而状态2输入输入1到达到达K2集故将集故将k1分为分为K11=1,K12=2 由于状态由于状态3，和，和 4 输入输入1，或，或0 都到达都到达k2集所以状态集所以状态3，4等价。等价。则可以分割成三个子集：则可以分割成三个子集：1，2，3，4 所以将DFA最小化的状态图如下：3.请构造与正则式请构造与正则式R=(a*b)*ba(a|b)*等价的状态最少的等价的状态最少的DFA（确定有限自动机）确定有限自动机）解：解：（1）首先构造转换系统图：）首先构造转换系统图：（2）由系统转换图构造由系统转换图构造DFA（NFA确定化）确定化）设初态为设初态为S,A,B,G,F NFA确定化为确定化为DFA的过程：的过程：I Ia Ib(1)S,A,B,G,F (2)G,F (3)A,B,C,G,F(2)G,F (2)G,F (4)A,B,G,F(3)A,B,C,G,F (5)D,F,G,E,Z (3)A,B,C,G,F(4)A,B,G,F (2)G,F (3)A,B,C,G,F(5)D,F,G,E,Z (6)G,F,E,Z (7)A,B,E,Z,G,F(6)G,F,E,Z (6)G,F,E,Z (7)A,B,E,Z,G,F(7)A,B,E,Z,G,F (6)G,F,E,Z (8)A,B,C,E,Z,G,F(8)A,B,C,E,Z,G,F (5)D,F,G,E,Z (8)A,B,C,E,Z,G,F DFA 这状态图如下：这状态图如下：确定有限自动机图如下：（3）将）将DFA最小化：先将终态和非终态分成两个集最小化：先将终态和非终态分成两个集:K1=1,2,3,4,K2=5,6,7,8 对于对于K1中的中的3态输入态输入a则则进入进入K2集，而集，而1，2，4态输入态输入a仍然在仍然在K1中，故中，故K1可可一分为二一分为二K11=1,2,4和和K12=3;考察考察K11对于对于1，4态态输入输入b到达到达3态而态而2态输入态输入b到达到达4态。故态。故K11可一分为二可一分为二K111=1,4;K112=2最后考察最后考察K2输入输入a或或b都到达都到达K2集。则集。则DFA化简为化简为1，4，2，3，5，6，7，8四个子集。其状态图如下：四个子集。其状态图如下：