习题讲解1.doc
第二章2.1、考虑文法GS SaSbS|bSaS| (1)试说明此文法是二义性的。可以从对于句子abab有两个不同的最左推导来说明。(2)对于句子abab构造两个不同的最右推导。 (3)对于句子abab构造两棵不同的语法树。 (4)此文法所产生的语言是什么？ 解答：(a) 句子abab有如下两个不同的最左推导： S aSbS abS abaSbS ababS abab S aSbS abSaSbS abaSbS ababS abab 所以此文法是二义性的。(b) 句子abab的两个不同的最右推导： S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab(c> 句子abab的两棵不同语法树： (一) (二) (d) 此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成 的字符串。 2.2 从供选择的答案中，选出应填入 的正确答案。 已知文法GS的产生式如下： S (L)|aL L,S|S属于L(GS)的句子是 A ，(a,a)是L(GS)的句子，这个句子的最左推导是 B ，最右推导是 C ，语法树是 D ，句柄是 E 。供选择的答案：A： a a,a (L) (L,a)B,C： S (L) (L,S) (L,a) (S,a) (a,a) S (L) (L,S) (S,S) (S,a) (a,a) S (L) (L,S) (S,S) (a,S) (a,a)D： E： (a,a) a,a (a) a 2.3 试构造生成下列语言的上下文无关文法：(1) anbnci | n1,i0 (2) w | wa,b+，且w中a的个数恰好比b多1 (3) w | wa,b+，且|a|b|2|a| (4) w | w是不以0开始的奇数集 解答：(1) 把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S ABA aAb|abB cB|(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下： S aE|Ea|bSS|SbS|SSbE aEbE|bEaE|(3) 设文法开始符号为S，产生的w中满足|a|b|2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）： S aSBS|BSaS| B b|bb(4) S 奇数头整数奇数尾 |奇数头奇数尾 |奇数尾 奇数尾 1|3|5|7|9 奇数头 2|4|6|8|奇数尾 整数 整数数字|数字 数字 0|奇数头第三章3.1 从供选择的答案中，选出应填入下面叙述中 ？内的最确切的解答。有限状态自动机可用五元组（VT，Q，q0，Qf）来描述,设有一有限状态自动机M的定义如下： VT=0,1，Q=q0,q1,q2，Qf=q2，的定义为：（q0，0）=q1 （q1，0）=q2（q2，1）=q2 （q2，0）=q2M是一个 A 有限状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正则表达式表示为 C 。其含义为 D 。 供选择的答案:A: 歧义的 非歧义的 确定的 非确定的B:C： (0|1)* 00(0|1)* (0|1)*00 0(0|1)*0D： 由0和1所组成的符号串的集合； 以0为头符号和尾符号、由0和1所组成的符号串的集合； 以两个0结束的，由0和1所组成的符号串的集合； 以两个0开始的，由0和1所组成的符号串的集合。答案A: B: C: D:3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。(1)有穷自动机接受的语言是正则语言。（）(2)若r1和r2是上的正规式，则r1|r2也是。（）(3)设M是一个NFA，并且L(M)x,y,z，则M的状态数至少为4个。（）(4)令a,b，则上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（）(5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（） 答案(1) T (2) T (3) F(4) F (5) T (6) T3.3 描述下列各正规表达式所表示的语言。(1) 0(0|1)*0(2) (|0)1*)*(3) (0|1)*0(0|1)(0|1)(4) 0*10*10*10*(5) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案(1) 以0开头并且以0结尾的，由0和1组成的所有符号串。(2) |0,1*即由0和1组成的所有符号串。(3) 由0和1组成的符号串，且从右边开始数第3位为0。(4) 含3个1的由0和1组成的所有符号串。 |0,1+，且中含有3个1 (5) |0,1*,中含0和1的数目为偶数。 3.4 对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) =0,1上的含偶数个1的所有串。(4) =0,1上的含奇数个1的所有串。(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。(6) 不包含子串011的由0和1组成的符号串的全体。(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答案(1) 令Letter表示除这五个元音外的其它字母。 (letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2) A*B*.Z*(3) (0|10*1)*(4) (0|10*1)*1(5) 分析设S是符合要求的串，|S|=2k+1 (k0）。则 SS10|S21，|S1|=2k (k>0），|S2|=2k (k0）。且S1是0,1上的串，含有奇数个0和奇数个1。 S2是0,1上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：(00|11)*(01|10)(00|11)|(01|10)(00|11)*(01|10)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为：(00|11)*(01|10)(00|11)|(01|10)(00|11)*(01|10)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6)1*|1*0(0|10)*(1|)(7)接受w的自动机如下：对应的正规表达式：(1(01*0)*1|0)* 3.5 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机。答案先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：羊空菜羊狼空羊羊空狼羊菜空羊现给出一个NFA:M=(,Q,0,9,)其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9转形函数(0,羊)=1, (1,空)=2, (2,菜)=3, (2,狼)=5(3,羊)=4, (5,羊)=6, (4,狼)=7, (6,菜)=7(7,空)=8, (8,羊)=93.6 给出接受下列在字母表0,1上的语言的DFA。(1) 所有以00结束的符号串的集合。(2) 所有具有3个0的符号串的集合。答案(a) DFA M=(0，1，q0，q1，q2，q0，q2，)其中定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q0（q2，0）=q2 （q2，1）=q0(b)正则表达式: 1*01*01*01* DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q1（q2，0）=q3 （q2，1）=q2（q3，1）=q3 3.7构造等价于下列正规表达式的有限自动机。(1)10|（0|11）0*1(2)(0|1)*|(11)*答案(1) DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:（q0，0）=q1 （q0，1）=q2（q1，0）=q1 （q1，1）=q3（q2，0）=q3 （q2，1）=q1(2) DFA M=(0，1，q0，q0，q0，)其中定义如下:（q0，0）=q0 （q0，1）=q038设语言L是“能被5整除的十进制正整数”组成的集合， （1）试写出描述语言L的正规表达式；（2）画出识别语言L的状态转移图。解： （1）语言L的正规表达式为： (1|2|9)(0|1|9)*(0|5)|5 （2）识别语言L的状态转移图为：39写出能产生字母表x,y上的不含两个相邻的x,且不含两个相邻的的全体符号串的有限状态自动机。解：
