计算理论答案汇总.docx

1、第一章练习1.1 图给出两台 DFA M1 和 M2 的状态图. 回答下述有关问题.a. M1 的起始状态是 q1b. M1 的接受状态集是q 2c. M2 的起始状态是 q1d. M2 的接受状态集是q 1，q 4e. 对输入 aabb,M1 经过的状态序列是 q1，q 2，q 3， q1，q 1f. M1 接受字符串 aabb 吗？否g. M2 接受字符串 吗？是1.2 给出练习 2.1 中画出的机器 M1 和 M2 的形式描述.M1=(Q1, 1,q1,F1) 其中1）Q 1=q1,q2,q3,;2）=a,b;3） 1 为：a bq1q2q3q2 q1q3 q3q2 q14）q 1 是起

2、始状态5）F 1=q2M2=(Q2, 2,q2,F2) 其中1）Q 2=q1,q2,q3,q4;2）=a,b;3） 2 为：a bq1q2q3q4q1 q2q3 q4q2 q1q3 q43）q 2 是起始状态4）F 2=q1,q41.3 DFA M 的形式描述为 ( q1，q 2，q 3，q 4，q 5，u,d,q 3，q 3),其中 在表 2-3 中给出。试画出此机器的状态图。q1 q5q4q2 q3u du u u udddd1.6 画出识别下述语言的 DFA 的状态图。a)w | w 从 1 开始以 0 结束 b)w | w 至少有 3 个 1c) w | w 含有子串 0101d) w

3、 | w 的长度不小于 3，且第三个符号为 0e) w | w 从 0 开始且为奇长度，或从 1 开始且为偶长度 或f) w | w 不含子串 110g) w | w 的长度不超过 5001110,10010 01 10,10,110011 0 100,100,10,1110,1 00,10,10,100,110,100,110,1010 11 00,1 0,1 0,1 0,1 0,1 0,10,1h)w | w 是除 11 和 111 以外的任何字符 i)w | w 的奇位置均为 1j) w | w 至少含有 2 个 0，且至多含有 1 个 1k) ,0l) w | w 含有偶数个 0，或恰

4、好两个 1m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语言的 NFA，且要求符合规定的状态数。a. w | w 以 00 结束，三个状态b. 语言w | w 含有子串 0101，即对某个 x 和 y，w=x0101y ，5 个状态.1 1 10,10 0 000100111110 00,10 0,1 0,1110 0,10,1110 01 11 1 10 00 00 010,1 0,10,10 00,10 10,10 10,1c. 语言w | w 含有偶数个 0 或恰好两个 1 ，6 个状态。d. 语言0 ，2 个状态。e. 语言 0*1*0*0，3 个状态。f. 语言 ，1 个

5、状态。g. 语言 0*，1 个状态。2.11 证明每一台 NFA 都能够转换成等价的只有一个接受状态的 NFA。证明:设 NFA M=Q，, , q0,F，F=r i1， rik.添加一个状态 p 后，r i1， rik 分别向 p 引 箭头，将 ri1， rik 变为非接受状态，p 变为接受状态。又因为添加 箭头不影响 NFA 识别语言，所以命题成立。2.14 a 证明：设 M 是一台语言 B 的 DFA，交换 M 的接状态与非接受状态得到一台新的 DFA，则这台新的 DFA 是识别 B 的补集，因此，正则语言类受在补运算下封闭。b 举例说明：设 M 是一台识别语言 B 的 NFA，交换 M

6、 的接受状态与非接受状态得到一台新的 NFA，这台新的 NFA 不一定识别 B 的补集。NFA 识别的语言类在补集下封闭吗？解释你的回答。解：a. M 是 DFA, M 是Q,q 0,F,令 N=Q,q 0,Q-F,设 =12 n 是字母表上任意字符串，因为 M 与 N 均为 DFA,所以必然存在 Q 中状态序列 r0,r1,rn,使得：r 0=q0, (r i, i+1)=ri+1, i=0,n-11)若 rn F 则 B;2)若 rn F,则 rn Q-F,即 N 接受 ，若 B,所以 N 接受 B 的补集，即 B 的补集正则。所以，正则语言类在补运算下封闭。b. 设 B 为0。NFA M

7、：可识别它。依题对它作变换，得到 N：011 1010 0 00 00 1 0000则 N 识别的语言不是 B 的子集。所以交换 M 的接受状态与非接受状态得到的新的 NFA 不一定识别 B 的补集。但是由于 NFA 识别的语言类与 DFA 识别的语言类相同，即正则语言类。由 a 的证明，正则语言类在补运算封闭，可知，NFA 识别的语言类-正则语言类在补运算下封闭。若 NFA 识别语言 A，必有 等价的 DFA 识别 A,从而由 a 知，可交换 DFA 的接受与非接受状态构造识别 A 的补集的 DFA,则必有等价的 NFA 识别 A 的补集。只是，该 NFA 未必有原NFA 交换接受与非接受状

8、态构造而成。1.15 给出一个反例，说明下述构造不能证明定理 2.24，即正则语言类在星号运算下封闭。设N=（Q 1, 1,q1,F1）识别 A1。如下构造 N=（Q 1, 1,q1,F1） 。N 应该识别 A1*。a. N 的状态集是 N1 的状态集。b. N 的起始状态是 N1 的起始状态相同。c. F=q 1F 1。F 的接受状态是原来的接受状态加上它的起始状态。d. 定义 如下：对每一个 q 属于 Q 和每一个 a 属于 。解：设 N1 识别语言 A=至少含有一个 1，其中输入字母表为0，1 ，可知 A*=空串或至少含有一个 1。N1: N:按上述规定构造 N 的状态图如上。可以看出

9、L(N)=0,1*不等于 A*. 所以如此构造的 N 不一定识别A*.1.16 使用定理 2.19 中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。a)， b)，解：a), b)2.13 给出生成练习 2.4 中语言的正则表达式。(注: 答案不唯一)a. w | w 从 1 开始以 0 结束 1 *0.Fa ,),( ),( 111且若 或若10,1 0,110,1 0,1a,bab1 2aa,bba1 23a,bab12b12a a,baab123b123aba,bb. w | w 至少有 3 个 1 *1*1*1*.c. w | w 含有子串 0101 *010

10、1*.d. w | w 的长度不小于 3，且第三个符号为 0 0*.e. w | w 从 0 开始且为奇长度，或从 1 开始且为偶长度 0()* 1()*.f. w | w 不含子串 110 (0 10) *1*.g. w | w 的长度不超过 5 .h. w | w 是除 11 和 111 以外的任何字符 0 * 10* 110* 111*.i. w | w 的奇位置均为 1 (1)*( 1).j. w | w 至少含有 2 个 0，且至多含有 1 个 1 0*(00 010 001 100) 0*.k. ,0. 0.l. w | w 含有偶数个 0，或恰好两个 1 (1*01*0)*1*

11、0*10*10*.m. 空集. .n. 除空串外的所有字符串 *.1.19 对下述每一个语言，给出 4 个字符串，2 个是这个语言的成员，2 个不是这个语言的成员。这里假设字母表 =a,b.a. a*b* 成员：ab，aab 非成员：aba，bab. a(ba)* 成员：ab ， abab 非成员：abb，aac. a* b* 成员：aaa，bbb 非成员：ab，bad. (aaa)* 成员：aaa，aaaaaa 非成员：a，aae.*a*b*a* 成员：aba，aaba 非成员：aa，abbf. aba bab 成员：aba，bab 非成员：a，bg. ( a)b 成员：b，ab 非成员：a

12、，bbh. (a ba bb) * 成员： a，bb 非成员： ，b1.21 使用引理 2.32 中叙述的过程，把图 2-38 中的有穷自动机转换成正则表达式。a), b),解: a) a*b(a ba*b)*b) (a b)a*b(aa ab b)a*b*(a ).(注：答案不唯一)1.29 利用泵引理证明下述语言不是正则的。a. A1=0n1n2n | n 0。证明：假设 A1 是正则的。设 p 是泵引理给出的关于 A1 的泵长度。令 S=0p1p2p,bab1 2abba,baa1 23S 是 A1 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满

13、足泵引理的 3 个条件。根据条件 3，y 中只含 0，xyyz 中，0 比 1、2 多，xyyz 不是 A1 的成员。违反泵引理的条件 1，矛盾。A 1 不是正则的。b. A2=www | w a,b*.证明：假设 A2 是正则的。设 p 是泵引理给出的关于 A2 的泵长度。令 S=apbapbapb,S 是 A2 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理的 3 个条件。根据条件 3，y 中只含 a，所以 xyyz 中第一个 a 的个数将比后两个 a 的个数多，故 xyyz 不是 A2 的成员。违反泵引理的条件 1，矛盾。A 2 不是正则

14、的。c. A3=a2n | n 0.(在这里，a 2n 表示一串 2n 个 a .)证明：假设 A3 是正则的。设 p 是泵引理给出的关于 A3 的泵长度。令 S= a2p，S 是 A2 的一个成员且 S 的长度大于 p，所以泵引理保证 S 可被分成 3 段 S=xyz 且满足泵引理的 3 个条件。即对任意的 i 0，xy iz 都应在 A3 中，且 xyiz 与 xyi+1z 的长度都应是 2 的幂. 而且 xyi+1z 的长度应是 xyiz 的长度的 2n 倍(n 1)。于是可以选择足够大的 i，使得|xy iz|=2np. 但是|xy i+1z|-|xyiz|=|y| p. 即|xy i

15、+1z|0。由泵引理条件3 知，|xy|p，故 y 一定由 0 组成，从而字符串 xyyz 中 1 前后 0 的数目不同，即 xyyz 不属于该语言，这与泵引理矛盾。所以该语言不是正则的。b) 假设0 n1n|n0 的补集是正则的，则根据正则语言在补运算下封闭可得0 n1n|n0 是正则的，这与已知矛盾，故假设不成立。所以该语言不是正则的。记 c=0m1n|mn ，c 为 c 的补集，c 0 *1*=0n1n|n0 ，已知0 n1n|n0 不是正则的。若 c 是正则的，由于 0*1*是正则的，那么 c 0 *1*也应为正则的。这与已知矛盾，所以 c 不是正则的。由正则语言在补运算下的封闭性可知

16、 c 也不是正则的。c) w | w0,1*不是一个回文的补集是w | w0,1*是一个回文 ，设其是正则的，令 p 是由泵引理给出的泵长度。取字符串 s=0p1q0p，显然 s 是一个回文且长度大于 p。由泵引理条件 3 知|xy|p，故 y 只能由 0 组成。而 xyyz 不再是一个回文，这与泵引理矛盾。所以 w | w0,1*是一个回文 不是正则的。由正则语言在补运算下的封闭性可知w | w0,1*不是一个回文 也不是正则的。1.31 对于任意的字符串 w=w1w2wn，w 的反转是按相反的顺序排列 w 得到的字符串，记作 wR，即wR=wnw2w1。对于任意的语言 A，记 AR=wR

17、| A证明：如果 A 是正则的，则 AR 也是正则的。证明：因为 A 是正则语言，所以可以用 NFA 来表示该语言，现在来构造 AR 的 NFA，将 NFA A 中的接受态变为中间态，起始态变为接受态，再添加一新的起始态，并用 箭头连接至原来的接受态，其它所有的箭头反向。 经过变换后得到 NFA 变成描述 AR 的 NFA.1.32 令 3 包括所有高度为 3 的 0 和 1 的列向量。 3 上的字符串给出三行 0 和 1 的字符串。把每一行看作一个二进制数，令B= w 3* | w 最下面一行等于上面两行的和 例如，证明 B 是正则的。证明：由题设 B 的定义可知，w 上面两行之和减去下面一

18、行结果为零，由此可设计 NFA M (Q, , , q0, F)，其中 = 3。Q=q 0,q1。q 0 状态表示上一次运算的进位为 0，q 1 状态表示上一次运算的进位为 1。 由下表给出：000001010011100101110111q0 q0 q0 q0 q1 q1 q0 q1 q1 q1000001,010, , ,1113=, 而B B001100110001101F=q0状态图为：所以可知自动机 M 识别的是语言 BR，因此 BR 是正则的。由题 2-24 的结论可知 B 也是正则的。1.33 令2 包含所有高度为 2 的 0 和 1 的列。 2 上的字符串给出两行 0 和 1

19、的字符串。把每一行看作一个二进制数，令C= w 2* | w 下面一行等于上面一行的 3 倍 。证明 C 是正则的。可以假设已知问题 2.24 中的结果。证明：如下的 NFA 识别 CR：其中 q0 状态表示上一次运算的进位为 0，q1 状态表示上一次运算的进位为 1, q2 状态表示上一次运算的进位为 2。如下的 NFA 识别 C：其中状态 q0,q1,q2 分别表示目前读到的下面的数减上面的数的 3 倍余 0,1,2 的情况。1.34 令2 包含所有高度为 2 的 0 和 1 的列。 2 上的字符串给出两行 0 和 1 的字符串。把每一行看作一个二进制数，令D= w 2* | w 上一行大于下一行 。证明 D 是正则的。证明：由题设可设计自动机 M=(Q, , , q, F)，其中 Q=q1,q2，F=q 2,转移函数与状态图为：00011011q1 q1 q2 q1q2 q2 q2 q2 q2, , ,2= 00 01 1110q0 q1001110101101000111100010, , , ,q0 q1 q200 1111000110q0 q1 q200 1101101100, , ,2= 00 01 1110