形式语言与自动机理论-蒋宗礼-第二章参考答案

《形式语言与自动机理论-蒋宗礼-第二章参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2．1回答下面的问题：（周期律02282067）（1）在文法中，终极符号和非终极符号各起什么作用？ü终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语言中字符的范围。ü非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。（2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ü文法的非终结符号A所对应的语法范畴代表着一个集合L（A），此集合由文法产生式中关于A的产生式推导实现的ü开始符号所对应的语法范畴则为文法G={V，

2、T，P，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）什么叫左线

6、性文法？什么叫右线性文法？什么叫线性文法ü文法G={V，T，P，S}，如果对于，所有均有：成立，则称Ｇ为线性文法。ü文法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证明得到的，可以在以后的推论中直接应

7、用的。*******************************************************************************2.设L={0n

8、n≥1},试构造满足要求的文法G.(1)G是RG.(2)G是CFG,但不是RG.(3)G是CSG,但不是CFG.(4)G是短语结构文法,但不是CSG.解答：1：S→0

9、0S2：S→0

10、0S

11、SS3：S→0

12、0S

13、ASAS→SAAS→0A0A→S00AS→004：S→0

14、0S

15、ASAS→SA