自动机重点复习题

《自动机重点复习题》由会员分享，可在线阅读，更多相关《自动机重点复习题（11页珍藏版）》请在金锄头文库上搜索。

1、第二章 Give DFAs accepting the following language: The set of all string ending in 00. The intuitive meanings of states A, B, and C are that the string seen so far ends in 0, 1, or at least 2 zeros. 状态 A, B，C 分别表示以,和 00 结尾的串的状态。 0 1 -A B A B C A *C C A Convert to a DFA the following NFA. 下表就是利用子集构造法将 N

2、FA 转化成的 DFA。其中构造的子集有：A = p; B = p,q; C = p,r; D = p,q,r; E = p,q,s; F = p,q,r,s; G = p,r,s; H = p,s. 0 1 -A B A B D C C E A D F C *E F G *F F G *G E H *H E H -NFA(convert to DFA 、-closure) (a): 根据状态的 闭包的的性质。求得， p 的 闭包：p； q 的 闭包：p,q； r 的 闭包：p,q,r。 b) 由于输入 a 状态总是保持不变， 因此只需考虑输入 b 和 c 的情况。 可以看出， 从状态 p 第

3、一次到 r 且只经过 b，c 和 转移的路径为 bb, bc 和 c ；到 r 之后， 读入 b 仍可回到 r，读入 c 回到 p ，则可通过继续读入串 bb, bc 和 c 回到 r。 因此，每一个由 b 和 c 组成的长度小于等于 3 的串可以被接受，除了串 b 不能接 受。向这些串中插入 a，并保持长度小于等于 3，就会得到所有由 a，b，c 组成 的，至多含有一个 a 的可被接受的串。由一个 c 和两个 a 组成的任意串也是可以 被接受的。其它的串均被拒绝。 由初始状态， 即 p 的 闭包或者p， 有 3 个状态可以达到。 令 A = p, B = p,q, C = p,q,r。转移表

4、如下： a b c -A A B C B B C C *C C C C 第三章 Rij(0) Rij(1) a) 下面就是所有 R0 的表达式；我们只写出下标： R11 = +1；R12 = 0; R13 = (phi); R21 = 1; R22 = ; R23 = 0; R31 = (phi); R32 = 1; R33 = +0. b) 下面就是所有 R(1) 的表达式；我们只写出下标：R11 = 1*; R12 = 1*0; R13 = phi; R21 = 11*; R22 = +11*0; R23 = 0; R31 = phi; R32 = 1; R33 = +0. e): Her

5、e is the transition diagram 转移图: 如果消除状态 q2，有: q1 到 q3 的正则表达式：1 + 01 + 00(0+10)*11*00(0+10)* Regular expression for: (1) the set of string that consists of alternating 0s and 1s. （+1） （01）*（+0） (2) a,b,c上包含至少一个 a 和至少一个 b 的集合。 首先考虑第一个 a 在第一个 b 的前面，然后再考虑相反的情况。表达式为： c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c

6、)* (3) 使得每对相邻的 0 都出现在任何一对相邻的 1 之前的所有 0 和 1 的串集 (10+0)*(01+1)*(+0) 第四章 只有只有1构成且长度为素数的所有串构成的语言不是正则语言构成且长度为素数的所有串构成的语言不是正则语言 00n n1010n n | n=1| n=1，证明下列语言不是正则的 令n为泵引理常数 （这个n与语言L的定义中的局部变量n无关） 。 设w = 0n10n。 把 w 打断为 w = xyz，满足|xy| =1，context-free grammar S - 0S1 | 01 aibjck | i!=j or j!=k S - AB | CD A -

7、 aA | B - bBc | E | cD C - aCb | E | aA D - cD | E - bE | b 意思如下: A 产生 0 或者一个或多个 a。. D 产生 0 或者一个或多个 c。 E 产生一个或多个 b。 B 产生式中 b 和 c 的个数一样多， 然后产生一个或多个 b (通过 E) 或 一 个或多个 c 通过 cD)。即， B 产生这样的字符串 b*c* ，其中 b 和 c 的 个数不相等。 同样， C 产生 a 和 b 个数不相等的字符串。 因此，AB 产生字符串 a*b*c* ，并且 b 和 c 的数目不同； CD 产生字 符串 a*b*c*并且 a 和 b 的

8、数目不同。 第六章 Design a PDA that processes sequence of ifs and elses, where i stands for if and e stands for else. 0n1n | n=1，Design a PDA that can accept the following language: 以空栈方式接受。符号 X 表示符号 0。初始状态 q 中不包含 1，我们每碰到一个 0 就把符号 X 压入栈中。 第一个符号 X 代替了初始符号 Z0。当碰到 1 时，我 们就进入状态 p，并且出栈，每输入一个 1 就有一个符号 X 出栈。下推自动机

9、PDA 是 PN=(q,p,0,1,X,Z0,q,Z0)。规则如下： 1. (q,0,Z0) = (q,X) 2. (q,0,X) = (q,XX) 3. (q,1,X) = (p,) 4. (p,1,X) = (p,) Convert the grammar to a PDA that accepts the same language by empty stack. G=(V,T,Q,S)是一个 CFG，构造以空栈方式接受的 PDA： P=（q，T，VT，转移函数，q，S） (q,0,1),0,1,A,S,q,S) 其中 定义为： 1. (q,S) = (q,0S1), (q,A) 2.

10、(q,A) = (q,1A0), (q,S), (q,) 3. (q,0,0) = (q,) 4. (q,1,1) = (q,) 第七章 unit productions、useless symbols 、CNF a) Eliminate null productions S 是可空的，所以任意生产式体中的 S 可以消去，也可以保留。因为没有体中只有 S 的产生 式，所以不必引入部分消去的规则。所求结果为 S - ASB | AB A - aAS | aA | a B - SbS | bS | Sb | b | A | bb b) Eliminate unit productions B-A

11、是仅有的单位产生式。于是用 A 的产生式的体替代该产生式的体 A 即得 S - ASB | AB A - aAS | aA | a B - SbS | bS | Sb | b | aAS | aA | a | bb c) Eliminate any useless symbols in the resulting grammer. 观测可得 A 和 B 都能推导出终结符号串，S 也是，所以没有无用符号。 d) change the grammer into CNF 引入新变元和新产生式 C-a 和 D-b，将新变元替代产生式中的终结符得 S - ASB | AB A - CAS | CA |

12、a B - SDS | DS | SD | b | CAS | CA | a | DD C - a D - b 最后处理长度为 3 的几个产生式， 比如 CAS 出现了两次。 引入新变元 E、 F 和 G 来拆分这些产生式的体部分，于是得到 CNF 文法如下： S - AE | AB A - CF | CA | a B - SG | DS | SD | b | CF | CA | a | DD C - a D - b E - SB F - AS G - DS aibjck | i=1，Design a TM accepting the language. 开始时，在带上给定 0 和 1 的有穷

13、序列，前后都是无穷的空格。交替的，这个 TM 将把一个 0 改成 X，然后把一个 1 改成 Y，直到所有的 0 和 1 都已经匹配了 为止。Design TM for the following language: The set of strings with an equal number of 0s and 1s. TM 转移表如下： state 0 1 B X Y q0 (q2,X,R) (q1,X,R) (qf,B,R) - (q0,Y,R) q1 (q3,Y,L) (q1,1,R) - - (q1,Y,R) q2 (q2,0,R) (q3,Y,L) - - (q2,Y,R) q3

14、(q3,0,L) (q3,1,L) - (q0,X,R) (q3,Y,L) qf - - - - - 说明：TM 在带上来回反复移动。符号 X 和 Y 用来代替相互抵消的 0 和 1。区 别是：在 X 左边没有不匹配的 0 和 1(因此带头移动从不会越过 X 的左边)，而在 Y 的左边有 0 或者 1。 开始时处于状态 q0，TM 寻找 0 或者 1，并记住其状态(看到 1 记 q1，看到 0 记 q2)，再将其改为 X。作为一种例外，若 TM 进入状态 q0 时看到空格，则所有的 0 和 1 已经匹配，因此进入状态 qf 输入被接收。处于状态 q1，TM 向右移动，寻找 0。 若找到， 则用 Y 代替 0， TM 进入状态 q3 并开始向左移动寻找 X。 类似地， 在状态 q2 寻找 1 匹配 0。 在状态 q3，TM 向左移动直到找到最右的 X。这时重新进入状态 q0，向右移动 越过 Y 直到看到 0，1 或者空格，循环重新开始。