搜索
词法分析补充习题1.构造与正规式(a|ba)*等价的状态最少的DFA。2.构造与正规式(a|b)*a(a|b)等价的状态最少的DFA。3.构造与正规式(a|b)*aa等价的状态最少的DFA。1.解答：(1)构造NFA如图1所示：图1（a｜ba）*的NFA（2）NFA确定化为DFA的过程如下表所示：IIaIb①{S,A,Z}②{A,Z}③{B}②{A,Z}②{A,Z}③{B}③{B}②{A,Z}Φ①②③为重新标注的状态号。画出相应的状态图如图2所示。图2（a｜ba）*的DFA（3）DFA最小化首先得到两个子集K1={3}和K2={1，2}。考察K2，由于{1，2}a={2}K2，{1，2}b={3}K1，所以K2不可再分。用1来代表K2并删除3，得到最小化DFA的状态图，图3所示.AZSaBabεε213aabab图3正规式（a｜ba）*的最小化DFA2.解答（1）构造NFA，见图1图1正规式(a|b)*a(a|b)的NFA（2）NFA确定化为DFA的过程表和相应DFA的状态图，见图2IIaIb①{S,A,B}②{A,B,C}③{A,B}②{A,B,C}④{A,B,C,Z}⑤{A,B,Z}③{A,B}②{A,B,C}③{A,B}④{A,B,C,Z}④{A,B,C,Z}⑤{A,B,Z}⑤{A,B,Z}②{A,B,C}③{A,B}①②③④⑤为重新标注的状态号。画出相应的状态图如图2所示。AZaSBCbεεaab1aa3b图2正规式(a|b)*a(a|b)的DFA（3）将DFA最小化并得到最小化的状态图，见图3首先进行初始划分得到两个子集：K1={1,2,3}和K2={4，5}考察K1：因{1,2,3}a={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,3}a={2}K1，{1,3}b={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的状态图如下所示：图3正规式(a|b)*a(a|b)的最小化DFA注（思考）：本题图1中的ε可省去，便可简化DFA的构建过程，见题3。25a13baaaba4bbb4a2aab15bbab3.解答：(1)构造NFA如图1所示：图1（a｜b）*aa的（NFA虚框内去掉）（2）NFA确定化为DFA的过程如下表所示：IIaIb①{S,A}②{A,B}③{A}②{A,B}④{A,B，Z}③{A}③{A}②{A,B}③{A}④{A，B，Z}④{A,B，Z}③{A}相应的状态图如图2所示。图2（a｜b）*aa的DFA（3）DFA最小化首先得到两个子集K1={1,2,3}和K2={4}。考察K1：由于{1,2,3}a={1,2，4}K1，也K2，所以K1可需要被分割。又因为{1,3}a={2}，{1,3}b={3}，所以将原状态集合分割成以下子集：K11={2}，K12={1，3}。目前划分得到的子集为：K11={2}，K12={1，3}，K2={4}。考察K12：{1,3}a={2}K1，{1,3}b={3}K1，所以K1不可再分割。状态1和状AZSaabεε42aababBa31abb态3可合并为同一状态。得到最小化DFA的状态图图3所示，图3正规式（a｜b）*aa的最小化DFA3a2b1baba