第一部分习题.doc-得力文库

资源描述

《第一部分习题.doc》由会员分享，可在线阅读，更多相关《第一部分习题.doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流第一部分习题【精品文档】第 8 页第一章习题1.书p36 2.3解：（a）首尾均为0的二进制串（b） 0，1组成的二进制串，包括空串（c）倒数第3位为0的二进制串（d）包含且仅包含3个1的二进制串（e） 1的个数和0的个数均为偶数的二进制串为检验是否确切的描述，需要通过正反两方面来思考。反过来还需要考虑，任何出偶数个0和偶数个1构成的串是否都在这个语言中。这实际上是问，每个这样的串，其结构是否都符合(e)中正规式所做的刻画。我们可以这样叙述由偶数个0和偶数个1构成的串，从左向右，每两个字符一组地考察，它 1由若干个(强调一下，可以是零个)00或1

2、1开始(这由正规式(00|11)*描述)；2一旦出现1个01或10，那么经过若干个00或11后，一定会出现1个01或10。这第二个01或10的后而可能还有若干个00或11，一直到串的结束，或者到再次出现01或者10为止。如果串没有结束的话，就是重复出现这里所描述的结构(所以，这由(01|10)(00|11)*(01|10)(00|11)*)*描述)。那么这种描述是否是最简的呢？满足要求的最简单的串有：(1)00(2)11(3) (01|10)(00|11)*(01|10)它们任意多次的重复构成的中仍然满足要求因此最简的串可以写成(00|11|(01|10)(00|11)*(01|10)*。2.

3、写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。分析有了上一题的结果，这个问题应该容易解决。首先给上一题的正规式起个名字： even_0_even_1 ( 00 | 11 | (01|10) (00|11)* (01|10) )* 对于偶数个0和奇数个1构成的串，其第一个字符可能是0或1。 1如果是1，那么剩下的部分一定是偶数个0和偶数个1（即1 even_0_even_1）。 2如果是0，那么经过若干个偶数个0或偶数个1，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。这样，正确的正规定义是：答案 ev

6、1 | e ) | no_0-1answer (0 | no_0 0 ) (no_0 0 )* (no_0 | e ) | no_0分析本题和上面一样，关键是找到一种合适的看待这种句子结构的观点。我们的观点是这样，每个这样的句子由若干个0把它分成若干段，如123031357106678035590123可以看成123, 0, 313571, 0, 6678, 0, 3559, 0, 123由0隔开的每一段，如313571，它不含0，并且又可以看成是由若干个1把它分成若干段。如此下去，就能找到该语言的正规定义。按这个思路，上面的正规定义应该逆序看。answer (0 | no_0 0 ) (n

7、o_0 0 )* (no_0 | e ) | no_0表示一个句子由若干个0分成若干段，特殊情况是整个句子不含0。在这个正规定义中，所引用的no_0表示不含0的串，它的定义和这个定义的形式一样，因为串的形式是一样的，只不过没有数字0。所以有no_0 (1 | no_0-1 1 ) (no_0-1 1 )* (no_0-1 | e ) | no_0-1其中no_0-1表示不含0和1的串。依此类推，最后no_0-8是表示不含0, , 8的没有重复数字的串，它只可能是单个9。4. 将图1.13的DFA极小化。aa开始0123abbbbb4图1.1 一个DFA012bbbb4aa开始图1.2 最简DF

8、A答案最简DFA见图1.2。分析本题要注意的是，在使用极小化算法前，一定要检查一下，看状态转换函数是否为全函数，即每个状态对每个输入符号都有转换。若不是全函数，需加入死状态，然后再用极小化算法。最后再把死状态删除。有些教材上没有强调这一点，有的习题解上的示例甚至忽略了这一点，本题将告诉你，这一点是重要的。本题加入死状态5后的状态转换图见图1.3。0123aabbabbb开始45aaa, b图1.3 加入死状态后的DFA使用极小化算法，先把状态集分成非接受状态集0, 1, 2, 3, 5和接受状态集4这两个子集。1集合4不能再分解，我们看集合0, 1, 2, 3, 5。move (0, 1,

9、 2, 3, 5, a) = 1, 2, 5move (0, 1, 2, 3, 5, b) = 3, 4, 5由于b 转换的结果3, 4, 5不是最初划分的某个集合的子集，因此0, 1, 2, 3, 5需要再分，由于状态1和状态2的b转换都到状态4。因此状态集合的进一步划分是：1, 2，0, 3, 5和42由于move (1, 2, a) = 2, 5move (1, 2, b) = 4move (0, 3, 5, a) = 1, 5move (0, 3, 5, b) = 3, 5显然1, 2和0, 3, 5需要再分，分别分成：1和2以及0, 3和53由于move (0, 3, a) = 1m

10、ove (0, 3, b) = 3因此不需要再分。这样状态0和状态3合并成一个状态，我们取0为代表，再删去死状态5，就得到该题的结果。如果不加死状态，我们来看一下极小化算法的结果。最初的划分是0, 1, 2, 3和4。1状态集合的进一步划分是：1, 2，0, 3和401bbaastarta4图1.4 一个不正确的结果2忽略了死状态的影响，会认为它们都不需要再分，此时得到的DFA如图1.4。显然，它和原来的DFA不等价。5. 一个C语言编译器编译下面的函数时，报告parse error before else。这是因为else的前面少了一个分号。但是如果第一个注释/* then part */误

11、写成/* then part那么该编译器发现不了遗漏分号的错误。这是为什么？long gcd(p,q)long p,q; if (p%q = 0)/* then part */return q else/* else part */return gcd(q, p%q);答案此时编译器认为/* then part return q else/* else part */是程序的注释，因此它不可能再发现else 前面的语法错误。分析这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括

12、号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释始于双连字符（-），随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写成long gcd(p,q)long p,q; if (p%q = 0)- then part return q else- else part return gcd(q, p%q);6. 为正规式 (a|b)* a (a|b) (a|b) 构造NFA。答案该正规式的状态转换图见图1.5。开始abaabab1234图1.5 接受正规式(

13、a|b)* a (a|b) (a|b)的NFA7. 用状态转换图表示接收(a|b)*aa 的DFA。该正规式表示的语言是，字母表上最后两个字符都是a的串的集合。抓住这个特点，我们首先画出构造过程中的第一步，见图1.6。它表明最简单的句子是aa。开始aa012图1.6 构造过程的第一步然后，因为在第一个a前可以有若干个b，因此状态0有到自身的b转换。在最后两个字符都是a的串的末尾添加若干个a，能够保持串的这个性质，因此状态2有到自身的a转换。这样我们有图1.7。开始aaab012图1.7 构造过程的第二步最后，在状态1和状态2碰到b时，前面刚读过的a，不管连续有多少个，都不可能作为句子结尾的那

14、两个字符a，因此状态3和状态2的b转换回到状态0。所有状态的a转换和b转换都己给出，这就得到最后结果。开始aaab012bb图1.8 构造结果练习：构造 DFA，接受 0和1的个数都是偶数的二进制串。eg: 0011, 00, 1100, 1010, 111100解：状态0：偶数个0偶数个1状态1：奇数个1偶数个0 11001100状态2：奇数个0偶数个1状态3：奇数个0奇数个1练习2.12（a）解：两种方法：方法一：（1）根据算法2.4构造NFA（2）根据算法2.2将NFADFA（3）根据算法2.3将DFA简化方法二：ABCDabababab012aa, ba, b（1）直接构造NF

15、A（2）根据算法2.2将NFADFAA=0B=0,1C=0,1,2D=0,2abABABCDCCDDBA（3）根据算法2.3将DFA简化a, 划分状态集A, B，C,Db, A,B面临字母a时转到B,C，由于B,C分属于不同的状态集，故此状态集A,B需要进一步划分成ABc,考虑C,D,它面临字母a时转到B,C，而B,C分属于不同的状态集，故此状态集C,D需要进一步划分成CD由上面可以知道，最简的DFA包含四个状态集ABCD，这样前面的DFA就是最简的DFA。方法三：（1）直接构造DFA按照课堂所讲述的号外方法，直接构造DFA：任意的a,b串可以分属于以下几种情况:n 长度为1:a, bn 长度大于等于1，末尾两位为ab, aa,ba,bb0123456ababababababab画出DFA。其中 1: a, 2: b, 3: aa, 4: ab, 5: ba, 6: bb。（2）根据算法2.3将DFA简化识别注释的DFA

展开阅读全文