《形式语言与自动机理论-蒋宗礼-第二章参考答案.doc》由会员分享，可在线阅读，更多相关《形式语言与自动机理论-蒋宗礼-第二章参考答案.doc（13页珍藏版）》请在金锄头文库上搜索。
1、21回答下面的问题： （周期律 02282067）（1）在文法中，终极符号和非终极符号各起什么作用？ 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语言中字符的范围。 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。（2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ 文法的非终结符号A所对应的语法范畴代表着一个集合L（A），此集合由文法产生式中关于A的产生式推导实现的 开始符号所对应的语法范畴则为文法G = V，T，P，
2、S所产生的语言L（G）=（3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句型的语言。（4）文法中的归约和推导有什么不同？ 推导：文法G = V，T，P，S，如果则称在G中推导出了。 归约：文法G = V，T，P，S，如果则称在G中归约到。 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下（从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立
3、，递归下降，LL（1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR（1），LALR等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。（5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ 非空：根据字母表幂的定义：为字母表中个字符组成的。这样，当字母表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷
4、，这也使得研究失去意义（6）任意给定一个字母表，该字母表上的语言都具有有穷描述吗？为什么？ 错误，因为一个字母表上有不可数无穷多个语言，而有穷表示只可能是可数无穷多个，又因为不可数无穷集和可数无穷集不是一一对应的，所以存在这样的语言，他不存在有穷表示。（7）请总结一下，在构造文法时，可以从哪几个方面入手？ 我们可以将其类比于软件工程中的概念:-) 首先，也是最重要的一点，需求分析，我们需要知道需要构造的语言的特点，具体表现形式，以及一些需要注意的细节，通过一些特例提炼特点。 其次，概要设计，将语言从具体中抽象到符号上，按照其特性将其划分类别。 再次，详细设计，将每一部分抽象的成果具体化，将所有
5、细节符号化 再次，编码，将详细设计的结果用文法符号的语言表示出来 最后，测试，找出边缘数据，特殊数据进行测试。（8）按照文法的乔姆斯基体系，文法被分为几类？各有什么样的特点？分为四类： 文法G = V，T，P，S，对应的（）则为型文法或短语结果文法。 如果对于，均有成立，则称为型文法或上下文有关文法，对应的（）称为型语言。 如果对于，均有成立，且成立，则称为型文法，或上下文无关文法，对应的（）为型语言。 如果对于，所有均有：成立，其中则称为型文法，或正则文法，对应的（）称型语言。（9）什么叫左线性文法？什么叫右线性文法？什么叫线性文法 文法G = V，T，P，S，如果对于，所有均有：成立，则称
6、为线性文法。 文法G = V，T，P，S，如果对于，所有均有：成立，其中则称为右线性文法。 文法G = V，T，P，S，如果对于，所有均有：成立，其中则称为左线性文法。（10）既然已经定义2-10中允许RL包含空语句，那么定理2-6和定理2-7还有什么意义？ 此为定义与定理的区别，定义2-10是针对文法是的情况下，定义其产生式加上后仍为，的语言仍为，而定理2-6和定理2-7针对的前提条件是如果为，他们都是通过定义2-10证明得到的，可以在以后的推论中直接应用的。*2. 设L = 0n | n 1 ,试构造满足要求的文法G.(1) G是RG.(2) G是CFG, 但不是RG.(3) G是CSG,
7、 但不是CFG.(4) G是短语结构文法,但不是CSG.解答：1：S0|0S2：S0|0S|SS3：S0|0S|AS ASSA AS0A 0AS0 0AS004：S0|0S|AS ASSA|ABB ABBAS ABA| *3.设文法G的产生式集如下，试给出句子id+id*id的两个不同的推导和两个不同的归约 Eid|c|+E|-E|E+E|E-E|E*E|E/E|E*E|Fun(E) （褚颖娜 02282072）推导：(1)E=E+E=E+E*E=E+E*id= E+id*id=id+id*id(2)E=E*E=E*id=E+E*id=E+id*id=id+id*id归约：(1)id+id*i
8、d= E+id*id= E+E*id= E+E*E =E+E=E(2)id+id*id= E+id*id= E+E*id=E*id= E*EaSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccc 推导二： S=aSBC=aaSBCBC=aaaBCBCBC =aaaBBCCBC =aaaBBCBCC =aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccc 归约一、归约二分别为推导一和推导二的逆过程*5
9、句子abeebbeeba的一个推导如下： （陈伟芳 学号？）S=aAa 使用产生式SaAa =aSSa 使用产生式ASS =abAbSa 使用产生式SbAb =abSSbSa 使用产生式ASS =abeSbSa 使用产生式Se =abeebSa 使用产生式Se =abeebbAba 使用产生式SbAb =abeebbSSba 使用产生式ASS =abeebbeSba 使用产生式Se =abeebbeeba 使用产生式Se不能给出abeebbeeb的归约，因为由文法G中产生式推出的句子只有三种情况：头尾都是a,头尾都是b，或者只有一个e，而abeebbeeb上面三个条件都不符合，所以它不是文法G
10、的一个句子，当然也就不能给出它的一个归约了。*2.6 设文法G的产生式集如下,请给出G的每个语法范畴代表的集合.SaSa|aaSaa|aAaAbA|bbbA|bBBcB|cCCccC|DDDdD|d解:set(D)=d+set(C)= c2n dm| m2 n0set(B)= c n d m |m2 n1set(A)= bpcndm | p1, m2, n1set(S)= aqbpcndmaq| p1 ,m2, n1, q1*7给定如下文法，请用自然语言描述它们定义的语言。 （吴贤珺 02282047） AaaAaaB BBccD#cc DbbbD#解：该语言由四部分组成：第一部分是偶数个a（
11、至少有两个），第二部分是3的倍数个b（可以是0个），第三部分是两个“#”号，第四部分是偶数个c（至少有两个）。 A0B1B2B B0C1C2C C0D1D2D012D0B1B2B解：该语言的句子是字母表0,1,2上所有长度为3的倍数的字符串，且非空。 A0B1B2BB0C1B2BC0E1D2D012D0C1B2BE0E1D2D012解：观察发现C和E所对应产生式右部是相同的。所以将文法化简成如下的形式：A0B1B2BB0C1B2BC0C1D2D012D0C1B2B作出状态图如下：ABCD0, 1, 21, 2001, 21, 200, 1, 2F 可以看出从初始状态A到终态F，至少要经过ABCF的过程，所以字符串的长度至少为3。而且，到F只能经过C，如果到达C后走其它的路径，那么所经过的弧上的字符串都是以0为结尾，也就是要回到C，最后一个字符一定是0。这样，该文法所确定的语言就是所有倒数第2个字符是0的串。 SaBbAAaaSBAABbbSABB解：由于该文法所确定的语言一时不易看出，可以先考虑简单的形式： SaBbAAaaSBbbS不难看出，该文法所确定的语言为所有由ab和ba组成的串，且非空。这些串有一个特点，就是a和
