期末习题ppt课件

1、构造一个文法，产生只包含单个数字、加号、减号的表达式，如9-2+5、3-1、6等。,1,1、构造一个文法，产生只包含单个数字、加号、减号的表达式，如9-2+5、3-1、6等。,答：文法GS:SS+D|S-D|DD0|1|2|3|4|5|6|7|8|9,2,2、写一文法，使其语言是偶正整数的集合，要求：(1)允许0打头（含0）；(2)不允许0打头。,3,2、写一文法，使其语言是偶正整数的集合，要求：(1)允许0打头（含0）；(2)不允许0打头。,答：(1):ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2):ENT|DTFT|GND|1|3|5|7|9D2|4|6|8FN|0GD|0,4,3、一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法可能有哪些产生式？(3)找出该句子的所有短语、直接短语、句柄。,5,(1)串abbaa最左推导:SABSaBSaSBBSaBBSabBSabbSabbAaabbaa最右推导：SABSABAaABaaASBBaaASBbaaASbbaaAbbaaabbaa,(2)产生式包含有：SABS|Aa|AaBSBB|b,6,(3)该句子的短语有：a是相对A的短语是相对S的短语b是相对B的短语bb是相对B的短语aa是相对S的短语abbaa是相对S的短语,7,4、已知文法GA，写出它定义的语言描述GA:A0B|1CB1|1A|0BBC0|0A|1CC,8,4、已知文法GA，写出它定义的语言描述GA:A0B|1CB1|1A|0BBC0|0A|1CC,答：定义的语言由0、1符号串组成，串中0和1的个数相同,9,5、文法SS(S)S|(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。,10,5、文法SS(S)S|(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。,答：（）生成的是嵌套的括号（）是二义的，因为对于句子：()()，可以构造两棵不同的分析树。,11,6、请描述下面正规式定义的串，字母表为0，1。a)0*(10+)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0,12,6、请描述下面正规式定义的串，字母表为0，1。a)0*(10+)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0,答：a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串,13,7、为下边所描述的串集写正规式，字母表是a，b。a)以ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串,14,答：a)(a|b)*abb)(bb)*c)(a*ba*ba*)*d)b*ab*e)(a|b)*ab(a|b)*f)b*a*,15,8、构造一个NFA，接受字母表a,b上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA，以及最小状态DFA。,16,8、构造一个NFA，接受字母表a,b上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA，以及最小状态DFA。,3,1,2,a,a,b,b,b,NFA,17,1,1,