词法分析习题.doc
词法分析补充习题1. 构造与正规式(a|ba)*等价的状态最少的DFA。2. 构造与正规式(a|b)*a(a|b)等价的状态最少的DFA。3. 构造与正规式(a|b)* aa等价的状态最少的DFA。1. 解答：(1)构造NFA如图1所示：aZASbaB图1（aba）*的NFA（2）NFA确定化为DFA的过程如下表所示：IIaIbS, A, ZA, ZBA, ZA, ZBBA, Z 为重新标注的状态号。画出相应的状态图如图2所示。a2aba1b3图2（aba）*的DFA（3）DFA最小化首先得到两个子集K1 = 3 和 K2 = 1，2。考察K2，由于1，2a = 2 K2，1，2b = 3 K1，所以K2不可再分。用1来代表K2并删除3，得到最小化DFA的状态图，图3所示.b31aa图3 正规式（ab a）*的最小化DFA2. 解答（1）构造NFA，见图1 aaZCaBSAbb图1 正规式(a|b)*a (a|b)的NFA（2）NFA确定化为DFA的过程表和相应DFA的状态图，见图2 IIaIbS, 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, C A, B 为重新标注的状态号。画出相应的状态图如图2所示。a4a2aa1bab5bb3b图2 正规式(a|b)*a (a|b)的DFA（3）将DFA最小化并得到最小化的状态图，见图3首先进行初始划分得到两个子集：K1 = 1,2,3 和 K2 = 4，5考察K1：因1,2,3a=2,4 K1，也 K2，所以1,2,3可被重新划分。由于状态1和状态3输入a都到达状态2，输入b都到达状态3，而状态2输入a到达状态4，输入b到达状态5，所以将K1分割成：K11 = 1,3 和 K12 = 2目前划分得到的子集为：K11 = 1,3 , K12 = 2, K2 = 4，5考察K11：1,3a=2 K1，1,3b=3 K1，所以1,3无需重新划分。考察K2：因4，5 a=4,2 K11， K12， K2，所以K2可被重新划分。将K2分割成：K21=4，K22=5。目前划分得到的子集为：K11=1，3，K12 = 2，K21=4，K22=5最后，令状态1代表K11，并删除3，最小化DFA的状态图如下所示：2aaaba41bbb5图3 正规式(a|b)*a (a|b)的最小化DFA注（思考）：本题图1中的可省去，便可简化DFA的构建过程，见题3。3. 解答：(1)构造NFA如图1所示：aaaZBASb图1（ab）*aa的（NFA虚框内去掉）（2）NFA确定化为DFA的过程如下表所示：IIaIbS, A A, BAA, BA,B，ZAAA, BAA，B，ZA,B，ZA相应的状态图如图2所示。aaa142bbba3b图2（ab）*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，所以K1不可再分割。状态1和状态3可合并为同一状态。得到最小化DFA的状态图图3所示，aaba312bb图3 正规式（ab）* a a的最小化DFA
