词法分析习题

1、词法分析补充习题1. 构造与正规式(a|ba)*等价的状态最少的 DFA。2. 构造与正规式(a|b)*a(a|b)等价的状态最少的 DFA。3. 构造与正规式(a|b)* aa等价的状态最少的DFA。1.解答：(1)构造NFA如图1所示：(2)NFA确定化为DFA的过程如下表所示:IIaIbS, A, ZA, ZBA, ZA, ZBBA, Z 为重新标注的状态号。画出相应的状态图如图2所示。图 2 (a | ba) * 的 DFA(3) DFA最小化首先得到两个子集 K1 = 3和K2 = 1, 2。考察K2,由于1 , 2a = 2? K2 , 1 , 2b = 3? K1，所以K2不可再

2、分。用1来代表K2 并删除3，得到最小化DFA的状态图，图3所示.图3正规式(a | b a) *的最小化DFA2解答(1)构造NFA,见图1(2) NFA确定化为DFA的过程表和相应 DFA的状态图，见图2IIaIbS, A, BA, B, CA, BA, B, CA, B, C, ZA, B, ZA, BA, B, CA, BA, B, C, ZA, B, C, ZA, B, ZA, B, ZA, B, CA, B 为重新标注的状态号。画出相应的状态图如图2所示。图 2 正规式(a|b)*a (a|b)的 DFA(3)将DFA最小化并得到最小化的状态图，见图3首先进行初始划分得到两个子集：

3、Ki = 1,2,3和K2 = 4, 5考察Ki :因1,2,3a=2,4? Ki，也？ K2,所以1,2,3可被重新划分。由于状态 1和状态3 输入a都到达状态2,输入b都到达状态3，而状态2输入a到达状态4,输入b到达状态 5，所以将K1分割成：Kii = 1,3和Ki2 = 2目前划分得到的子集为：Kii = 1,3 , K12 = 2, K = 4，5考察 Ki仁1,3a=2? Ki, 1,3b=3? Ki，所以1,3无需重新划分。考察K2：因4, 5 a=4,2? Kii,?K12,?K2,所以K2可被重新划分。将K2分割成：K2i =4，K22=5。目前划分得到的子集为：Kii=i

4、, 3, K12 = 2, K21 =4, K22=5最后，令状态1代表Kii，并删除3,最小化DFA的状态图如下所示：图3正规式(a|b)*a (a|b)的最小化 DFA注(思考)：本题图1中的&可省去，便可简化 DFA的构建过程，见题 3。3.解答：(1)构造NFA如图1所示:图1 (a | b) *aa的(NFA虚框内去掉)(2) NFA确定化为DFA的过程如下表所示:IIalbS, A A, BAA, BA,B, ZAAA, BAA, B, ZA,B, ZA相应的状态图如图2所示。图 2 (a | b) *aa 的 DFA(3) DFA最小化首先得到两个子集 K1 = 1,2,3和K2 = 4。考察K1:由于1,2,3a = 1,2 , 4? K1,也？ K2,所以K1可需要被分割。又因为1,3a = 2, 1,3b = 3，所以将原状态集合分割成以下子集：K11=2, K12=1, 3。目前划分得到的子集为：K11=2, K12=1, 3, K2 = 4考察K12: 1,3a = 2? K1, 1,3b = 3? K1，