资源描述：
《词法分析习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、词法分析补充习题1.构造与正规式(a
2、ba)*等价的状态最少的DFA。2.构造与正规式(a
3、b)*a(a
4、b)等价的状态最少的DFA。3.构造与正规式(a
5、b)*aa等价的状态最少的DFA。1.解答：(1)构造NFA如图1所示：aεεZASbaB图1（a｜ba）*的NFA（2）NFA确定化为DFA的过程如下表所示：IIaIb①{S,A,Z}②{A,Z}③{B}②{A,Z}②{A,Z}③{B}③{B}②{A,Z}Φ①②③为重新标注的状态号。画出相应的状态图如图2所示。a2aba1b3图2（a｜ba
6、）*的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所示.b31aa图3正规式（a｜ba）*的最小化DFA2.解答（1）构造NFA，见图1aaZCaBεεSAbb图1正规式(a
7、b)*a(a
8、b)的NFA（2）NFA确定化为DFA的过程表和相应DFA的状态图，见图2IIaIb①{S,A,B}②{A,B,C}③{A,B}②{A,B,
9、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所示。a4a2aa1bab5bb3b图2正规式(a
10、b)*a(a
11、b)的DFA（3）将DFA最小化并得到最小化的状态图，见图3首先进行初始划分得到两个子集：K1={1,2,3}和K2={4，5}考察K1：因{1,2,3}a={2,4}ËK1，也ËK2，所以{1,2,3
12、}可被重新划分。由于状态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
13、={1，3}，K12={2}，K21={4}，K22={5}最后，令状态1代表K11，并删除3，最小化DFA的状态图如下所示：2aaaba41bbb5图3正规式(a
14、b)*a(a
15、b)的最小化DFA注（思考）：本题图1中的ε可省去，便可简化DFA的构建过程，见题3。3.解答：(1)构造NFA如图1所示：aaaZBεεASb图1（a｜b）*aa的（NFA虚框内去掉）（2）NFA确定化为DFA的过程如下表所示：IIaIb①{S,A}②{A,B}③{A}②{A,B}④{A,B，Z}③{A}③{A}②{
16、A,B}③{A}④{A，B，Z}④{A,B，Z}③{A}相应的状态图如图2所示。aaa142bbba3b图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}
17、a={2}ÌK1，{1,3}b={3}ÌK1，所以K1不可再分割。状态1和状态3可合并为同一状态。得到最小化DFA的状态图图3所示，aaba312bb图3正规式（a｜b）*aa的最小化DFA
