词法习题(参考答案2013)

词法分析习题参考答案1、构造下列正则式相应的DFA（1）1(0|1)*101解：NFANFA变换DFA的子集法过程重新命名：DFA状态转换图01-[0][1][1][1][12][12][13][12][13][1][124]+[124][13][12]01-01112232314+43200，12310141100231114011001（3）a((a|b)*|ab*a)*bNFA构造过程：或((a|b)*|ab*a)*baεbaε(a|b)*|ab*a(a|b)*ab*aba(a|b)*|ab*abaNFA到DFA构造过程：ΣSab0-[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：εε132a|bbaa04bab1b03a、a24ababba2．已知NFA…,构造相应的DFANFA矩阵NFA==DFADFA更名01-XZXYX,Y]+ZX,ZY01-[X][Z][X][Z][XZ][Y][XZ][XZ][XY][Y][XY]+[XY][XYZ][X]+[XYZ][XYZ][XY]01-01012322434+450+554DFA之状态转换图：0210050140103111=3．将图4.20确定化：解：NFA变换DFA的子集法过程01-[S][VQ][UQ][VQ][VZ][UQ][UQ][V][UQZ][V][Z]+[VZ][Z][Z]+[UQZ][VZ][UQZ]+[Z][Z][Z]重新命名：01-01214223536+466+545+666DFA状态转换图001Q1b1SZUV010，10，11530000042101b10，10，16114．把图4.21的（a）分别确定化和最小化确定化：重新命名：最小化：步骤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：ab–+[0][01][1]+[01][01][1][1][0]ab–+012+11220a,b103aa,b103aaa,b213aa03b5．构造一个DFA，它接收∑={0，1}上所有满足下列条件的字符串：每个1都有0直接跟在右边。然后再构造该语言的正则文法。DFA:正则文法:S→0S|1A|εA→0S7.构造DFANFA:A10S0XBaQASabba,baDbbbbbbbbabbNFA=DFA:DFA:8.给出下述文法所对应的正则式S→0A|1BA→1S|1B→0S|0解：用A和B定义的右部串，替换S定义的右部串中的A和B，得：S→01S|01|10S|10合并同类项和提取公因子得：S→(01|10)S|(01|10)ab-[S][A][Q][A][A][BX][Q][Q][DX]+[BX][Q][D]+[DX][A][B][D][A][B][B][Q][D]bbBXSaaAQaBXbaaababbDBbb在利用规则2（A→xA|y==A→x*y）得：S→(01|10)*(01|10)即所求的正则式为：(01|10)*(01|10)