第1章1．(1)×(2)√(3)×(4)×(5)×(6)√第2章1．(1)√(2)√(3)×(4)×(5)×(6)×2．（1）终结符：0，1，2，3，4，5，6，7，8，9，10非终结符：N，S，E，D（2）=1\*GB3①NSES10D10110=2\*GB3②NSES0SD0S10D101101DESN1D01110最右推导的语法树0ESNDS1（3）偶数的集合3．（1）句子abab的两个相应的最右推导：SaSbSaSbaSbSaSbaSbaSbabababSaSbSaSbabSaSbabSababab（2）此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。4．能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。所求文法G[S]:S→MF|5F→5|0N→1|2|3|4|5|6|7|8|9D→N|0M→MD|N其中，S代表能被5整除且不以0开头的无符号整数;F代表可以出现在个位上的数字;D代表所有数字;N代表所有非零数字;M代表不以零开头的数字串。5．（1）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε（2）设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS|BSaS|εB→b|bb（3）S→HMT|HT|TH→1|2|3|4|5|6|7|8|9T→1|3|5|7|9M→MN|NN→0|H其中，H代表奇数头，T代表奇数尾，M代表整数，N代表数字6．（1）1型（2）2型（3）3型7．正确的程序为：vara,b,c;beginread(a,b);c:=100;ifa>0thenbeginb:=b+1;write(b)end;write(a,b,c);end.8．(1)扩充条件语句的语法图为：EBNF的语法描述为：〈条件语句〉→if〈条件〉then〈语句〉[else〈语句〉](2)扩充repeat语句的语法图为：EBNF的语法描述为：〈repeat循环语句〉→repeat〈语句〉{；〈语句〉}until〈条件〉第3章1．(1)√(2)√(3)×(4)×(5)√(6)√(7)×(8)√(9)×(10)×2．注意正规式不唯一（1）(0|1)*01（2）1*01*（3）(11)*（4）(0*10*10*)*（5）(0|1)*01(0|1)*（6）1*0*3．（1）必须以x开头和x结尾的串（2）每个y至少有一个x跟在后边的串（3）所有含两个相继的x或两个相继的y的串4．12453othersothers/***/标记为others的边是指字符集中未被别的边指定的任意其它字符。分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。在这个DFA中，最容易忽略的是状态4到本身的’*’转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是’*’，那么把刚才读过的’*’看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象/****Thisisacomment****/这样的注释就被拒绝。另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。12453othersothers/***/6othersothersallall5．先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：①羊空菜羊狼空羊②羊空狼羊菜空羊现给出一个NFA:M=(Σ,Q,0,{9},f)其中Σ={羊，空，菜，狼}Q={0,1,2,3,4,5,6,7,8,9}转换函数f(0,羊)=1,f(1,空)=2,f(2,菜)=3,f(2,狼)=5,f(3,羊)=4f(5,羊)=6,f(4,狼)=7,f(6,菜)=7,f(7,空)=8,f(8,羊)=96．这个DFA和无