词法习题(参考答案015).docVIP

词法分析习题参考答案 1、构造下列正则式相应的DFA （1）1(0|1)* 101 解：NFA NFA变换DFA的子集法过程 0 1 -[0] [1] [1] [1] [1 2] [1 2] [1 3] [1 2] [1 3] [1 ] [1 2 4] +[1 2 4] [1 3] [1 2] 重新命名： 0 1 - 0 1 1 1 2 2 3 2 3 1 4 + 4 3 2 DFA状态转换图 （3）a((a | b)*| ab*a)*b NFA构造过程： 或 NFA到DFA构造过程： Σ S a b 0 -[0] 1 [1,2] 1 [1,2] 2 [1,2,3] 3 [1,2,4] 2 [1,2,3] 2 [1,2,3] 4 [1,2,3,4] 3 +[1,2,4] 2 [1,2,3] 3 [1,2,4] 4 +[1,2,3,4] 2 [1,2,3] 4 [1,2,3,4] DFA： 2．已知NFA…,构造相应的DFA NFA矩阵 0 1 -X Z X Y X, Y] +Z X, Z Y NFA ==DFA 0 1 - [X] [Z] [X] [Z] [X Z] [Y] [X Z] [X Z] [X Y] [Y] [X Y] +[X Y] [X Y Z] [X] +[X Y Z] [X Y Z] [X Y] 0 1 - 0 1 0 1 2 3 2 2 4 3 4 +4 5 0 +5 5 4 DFA更名 DFA之状态转换图： 3．将图4.20确定化： 解：NFA变换DFA的子集法过程 0 1 - [S] [V Q] [U Q] [V Q] [V Z] [U Q] [U Q] [V] [U Q Z] [V] [Z] +[V Z] [Z] [Z] +[U Q Z] [V Z] [U Q Z] +[Z] [Z] [Z] 重新命名： 0 1 - 0 1 2 1 4 2 2 3 5 3 6 +4 6 6 +5 4 5 +6 6 6 DFA状态转换图 4．把图4.21的（a）分别确定化和最小化 确定化： a b –+ [0] [01] [1] +[01] [01] [1] [1] [0] 重新命名： a b –+ 0 1 2 +1 1 2 2 0 最小化： 步骤1. 依据一致性条件，终态和非终态一定不等价。 将状态集 ｛0，1，2｝划分成如下两个子集： ｛0，1，2｝=｛0，1｝∪ ｛2｝ 步骤2：依据蔓延性条件，分解子集｛0，1｝： f(0,a)=1，f(1,a)=1 : 关于a不可分 f(0,b)=2，f(1,b)=2 : 关于b不可分 结论：子集｛0，1｝是不可分的，即0和1是等价的。 最小化DFA： 5．构造一个DFA，它接收∑={0，1}上所有满足下列条件的字符 串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。 DFA: 正则文法: S →0S | 1A | ε A →0S 7. 构造DFA NFA : NFA=DFA: a b - [S] [A] [ Q] [A] [A] [BX] [Q] [Q] [DX] + [BX] [Q] [D] +[DX] [A] [B] [D] [A] [B] [B] [Q] [D] DFA: 8. 给出下述文法所对应的正则式 S → 0A | 1B A → 1S | 1 B → 0S | 0 解：用A和B定义的右部串，替换S定义的右部串中的A和B，得： S→ 01S | 01 | 10S | 10 合并同类项和提取公因子得： S→ (01 | 10)S | (01 | 10) 在利用规则2（A → xA | y ==A → x*y）得： S→ (01 | 10)*(01 | 10) 即所求的正则式为：(01 | 10)*(01 | 10) a b ε ε a a b ((a | b)*| ab*a)* a 0 S 0 1 1 1 6 0，1 0，1 1 1b 0 1 2 4 0 0 0 0 0 3 5 0，1 0，1 1 0 V U Z S 1 1b Q 1 0 0 0 0 1 1 4