第二章习题解答.pptx

第三章 词法分析习题习题给一个语言（或者给一个正则表达式）给一个语言（或者给一个正则表达式）给给出出该该语语言言的的正正规规式式（或或者者根根据据已已知知的的正正则则表达式写出该语言的含义）（表达式写出该语言的含义）（3分）分）画出接收该语言的画出接收该语言的NFA（4分）分）把该把该NFA转换成等价的转换成等价的DFA（4分）分）对该对该DFA进行状态最小化（进行状态最小化（4分）分）题目类型：题目类型：7.构造下列正规式的DFA7.1 1(0|1)*101E10A1B0C1D1以以1打头，以打头，以101结尾的所有由结尾的所有由0和和1组成的符号串。组成的符号串。II0I1ABBBB,CB,CB,DB,CB,DBB,C,EB,C,E B,DB,C确定化确定化E10A1B0C1D101S0S1S1S1S2S2S3S2S3S1S4S4S3S201S0S1S1S1S2S2S3S2S3S1S4S4S3S241011021301001最小化最小化I=I(1)，I(2)=4,0,1,2,3 解解.初始划分初始划分:0:I(1)不能再被细分，考察不能再被细分，考察I(2)=0,1,2,30,1,2,30=1,2,3落入了落入了0,1,2,30,1,2,31=1,2落入了落入了0,1,2,3I(2)不能再被细分。所以，最小化后的不能再被细分。所以，最小化后的DFA如上图所示。如上图所示。7.2 1(1010*|1(010)*1)*0I1AB0CDE1010F11GH010以以1打头，以打头，以0结尾的。所有由结尾的。所有由0和和1组成的符号串。组成的符号串。8.给出下面正规表达式(8.1)以01结尾的二进制数串:(0|1)*01(8.2)能被5整除的十进制整数非0打头n=(1|2|3|9)+(0|5)(8.3)包含 奇数个0 或 奇数个1的二进制数串奇数个奇数个1：r1=0*1(0|10*1)*奇数个奇数个0：r2=1*0(1|01*0)*r=r1|r2(8.4)英英文文字字母母 组组成成的的所所有有符符号号串串,要要求求符符号号串串中中的的字字母母依依照照字字典典序序 排列排列(a|A)*(b|B)*(z|Z)*令：令：ri=i|，i=0,1,2,9P(0,1,2,9)表示表示0,1,2,9的全体排列的全体排列则：则：r=P(r0,r1,r9)(8.5)没有没有重复出现的数字重复出现的数字 的数字符号串的全体的数字符号串的全体(8.6)最多有最多有一个重复出现的数字一个重复出现的数字 的数字符号串的全体的数字符号串的全体令：令：ri=i|，i=0,1,2,9s=0|1|2|9|P(0,1,2,9)表示表示0,1,2,9的全体排列的全体排列则：则：r=P(r0,r1,r9,s)(8.7)不包含子串不包含子串abb 的由的由a和和b组成的符号串的全体组成的符号串的全体b*(a|ab)*ba213abIIaIb1,2 2,3 1,22,3 2,3 222,3aba102ba最小化？最小化？9.给出DFA及正规表达式(9.1)0,1 上的上的含有子串含有子串010的所有串的所有串(0|1)*010(0|1)*D0A1B0C0101I0I1AA,BAA,BA,BA,CA,CA,B,DAA,B,DA,B,DA,C,DA,C,D A,B,DA,DA,DA,B,DA,D确定化确定化01S0S1S0S1S1S2S2S3S0S3S3S4S4S3S5S5S3S501S0S1S0S1S1S2S2S3S0S3S3S4S4S3S5S5S3S50 1 2 3,4,5最小化最小化300110210101(9.2)0,1 上的 不含子串010的所有串1*(0|111*)*1*EAB1011CD11I0I1A,B,EB,EA,C,E,BB,EB,EC,EA,C,E,BB,EA,D,C,E,BC,ED,E,BA,B,C,D,EB,EA,C,D,E,BD,E,BB,EC,D,E,BC,D,E,BB,EC,D,E,B确定化确定化01012113214354145166160,1,2,3,4,5,60,2,4,5,6 1 30101011330最小化最小化I0I1A,B,EB,EA,C,E,BB,EB,EC,EA,C,E,BB,EA,D,C,E,BC,ED,E,BA,B,C,D,EB,EA,C,D,E,BD,E,BB,EC,D,E,BC,D,E,BB,EC,D,E,B130100110101011330补充:所有不含子串011的01串1*(01|0)*10.狼,山羊,白菜M:人人W:狼狼S:羊羊C:白菜白菜状态中间的横线代表河状态中间的横线代表河,横线上下两侧字母分别表示北岸和南岸横线上下两侧字母分别表示北岸和南岸现有的人或物现有的人或物,弧线上的字母表示正在过河的人和物弧线上的字母表示正在过河的人和物MWSCMSWC MSMMWC S SMWC WMCS CMWSMCMWMSMSW CMSMSC WMWMCMMSWCMS MWSCMWCSM:人人W:狼狼S:羊羊C:白菜白菜状态中间的横线代表河状态中间的横线代表河,横线上下两侧字母分别表示北岸和南岸横线上下两侧字母分别表示北岸和南岸现有的人或物现有的人或物,弧线上的字母表示正在过河的人和物弧线上的字母表示正在过河的人和物(12.a)确定化和最小化a01aa,bIIaIb00,110,10,1110021aabba02aab最小化结果最小化结果确定化结果确定化结果(12.b)确定化和最小化aaaaabbbbbb35240a1最小化ab0121142133324055540:0,12,3,4,51:0,12,4 3,5ab002203332023abaabb14.构造DFA,它接受=0,1上所有满足如下条件的字符串:每个1都有0直接跟在右边XY(0|10)*XY10201X2010XY1020101X,1,Y1,Y21,Y1,Y221,Y确定化确定化01XX22X最小化最小化X2010