《自动机理论、语言和计算导论》课后习题答案.docx

《自动机理论、语言和计算导论》课后习题答案（部分）@LIANGJIABINEx.5.1.1(b) 设计下列语言的上下文无关文法：b) 集合，即所有满足下列性质的集合：若干个后面跟着若干个b，若干个b后面跟着若干个c，并且或者a和b的数目不同，或者b和c的数目不同，或者两者数目都不同。解：Ex.5.1.2(c)下面文法产生了正则表达式的语言：试给出下列串的最左推导和最后推导。c) 00011。解：最左推导：最右推导：Ex.5.1.5设，可以把看做字母表的正则表达式所使用的字母表集合，惟一不同的是用来表示符号，目的是为了避免有可能出现的潜在的混淆，你的任务是以为终结符号来设计一个CFG，该CFG生成的语言恰好是字母表为的正则表达式。解：Ex.5.2.1对于习题5.1.2中的文法和每个串，给出相应的语法分析树。解：1）001012）10012）00011Ex.5.4.7(a)下面的文法生成的是具有x和y操作数、二元运算符+、-和*的前缀表达式：a) 找到串的最左推导、最右推导和一棵语法分析树。解：最左推导：最右推导：语法分析树：5.1.1(c) 设计下列语言的上下文无关文法：c) 所有不是形式的由和构成的串的集合，即不是把某个串重复一遍的串。解：Ex.6.1.1(b) Ex.6.2.5 (b)Ex.6.2.6 Ex.6.2.2 (b) CFG：PDA:Ex.6.3.2解：构造PDA 其中转移函数的定义如下：Ex.6.3.4解：PDA 的图形表示如下：转化为与之等价的以空栈方式接受的PDA ：其形式化定义如下：的定义如下：根据构造上下文无关文法其中，变元产生式集合定义如下：令，根据上面转移函数有：Ex.6.3.5(c)解：构造该语言的CFG 其中根据CFG构造以空栈方式接受同样语言的PDA 其中的定义如下：Ex.6.4.2(c)解：Ex.7.1.3解：a) 去除产生式：b) 去除单位产生式：c) 去除无用符号：不可达d) 转化为乔姆斯基范式：引入和Ex.7.1.9(b)解：首先证明其正确性，即证明该算法找出的符号都是可达符号。基础：开始符号是可达的。归纳：假设有一个产生式，并且是可达的，则也是可达的。注意，这条规则包括的情况。其次证明其完备性，即证明所有可达符号都可以通过该算法找出。基础：0步推导找出是可达符号。归纳：假设步推导的可达符号全部被找出，并且是其中任意一个，那么根据产生式可以得到也是可达符号，如此便可得到步推导的所有可达符号。综上，可证明算法恰好能够找出所有的可达符号。Ex.7.2.1(b)(c)解：b) ，对于任意，取，显然。任选满足条件：的，知只能包含一种符号或相邻的两种符号。如果只包含一种符号，分两种情况：如果只包含或，那么中的个数不等，因此；如果只包含，中的个数比的个数多，因此。如果包含相邻的两种符号，同样分两种情况：如果包含了和，那么中的个数比的个数少，因此；如果包含了和，那么中的个数比的个数少，因此。综上，根据CLF泵引理知不是上下文无关语言。b) ，对于任意，取，显然。任选满足条件：的，假设，则，取，则，显然其长度不是素数，故。根据CLF泵引理知不是上下文无关语言。Ex.7.2.1(d) 解：，对于任意，取，显然。任选满足条件：的。若只包含，那么所含的个数大于，而的个数为，因此；若只包含，那么所含的个数大于，而的个数为，因此；若同时包含和，那么中和的个数分别为和，而，因此；综上，根据CLF泵引理知不是上下文无关语言。Ex.7.3.1 证明CFL在下列运算下的封闭性。b) 如果是一个语言，是一个符号，则（称作和的商）是所有满足如下条件的串的集合：属于。例如，如果，则。提示：从语言的出发。证明：如果是一个，则存在一个，使得，假定。构造一个，使得，方法如下：；；，其中；；。令，下面我们如下两件事情：对任意的；对任意的；因为对任意的在中存在由一个最左推导：对应于在中的一个最左推导：Ex.7.3.2 考虑以下两个语言：通过分别给出上述语言的文法来证明这些语言都是上下文无关的。解：定义文法的产生式集合为：定义文法的产生式集合为：可以证明，。Ex.7.3.2 考虑以下两个语言：是吗？证明你的结论的正确性。解：不是，可以用泵引理证明：对于任意的，存在。令，其中，。取，则。因此，不是。Ex.7.3.6 给出定理7.25（如果是CLF，则也是。）的形式化证明：CLF在反转运算下是封闭的。证明：令，。构造，，其中中的每一个产生式是中产生式的反向，即当且仅当。下面用归纳法证明，对任意的，当且仅当。时，是中的一个产生式，是中的一个产生式，命题成立；时，设，其中，。若，则存在，使得在少于步内，，由归纳假设，；若，则令，自然有。于是有，。同理可证，如果，则有。由此可知，如果是CLF，则也是。Ex.7.4.3 对于例7.34中的文法，用CK