词法分析作业答案.ppt

《词法分析作业答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.求正则式（a

2、b)(a

3、b

4、0

5、1)*对应的正则文法（右线性文法），画状态转换图。解:(a

6、b):Sa

7、b(a

8、b

9、0

10、1)*:AaA

11、bA

12、0A

13、1A合并:Sa

14、bAaA

15、bA

16、0A

17、1A

18、εSABZa,b,0,1abεε2、求正则文法G[Z]：Z0Z

19、1Z

20、0AA0BB0对应的正则式:解:(0

21、1)*0002.已知有限自动机如图(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的有限自动机DFA.解：（1）L={W

22、W{0,1},并且W至

23、少有两个连续的1}（2）正则式为（0

24、1)*11(0

25、1)*正则文法G(Z)为：Z0Z

26、1Z

27、1AA1B

28、1B0B

29、1B

30、0

31、1（3）将图中有限自动机确定化：首先从处态A出发：II0I1(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到达

32、状态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

33、b)*等价的状态最少的DFA（确定有限自动机）解：（1）首先构造转换系统图：（2）由系统转换图构造DFA（NFA确定化）设初态为[S,A,B,G,F]NFA确定化为DFA的过程：IIaIb(1)[S,A,B,G,F](2)[G,F](3)[A,B

34、,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

35、,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，

36、4}，{2}，{3}，{5，6，7，8}四个子集。其状态图如下：