5034657600自动机理论语言和计算导论课后习题答案中文版.doc
《5034657600自动机理论语言和计算导论课后习题答案中文版.doc》由会员分享,可在线阅读,更多相关《5034657600自动机理论语言和计算导论课后习题答案中文版.doc(67页珍藏版)》请在三一文库上搜索。
1、 Solutions for Section 2.2Exercise 2.2.1(a)States correspond to the eight combinations of switch positions, and also must indicate whether the previous roll came out at D, i.e., whether the previous input was accepted. Let 0 represent a position to the left (as in the diagram) and 1 a position to th
2、e right. Each state can be represented by a sequence of three 0s or 1s, representing the directions of the three switches, in order from left to right. We follow these three bits by either a indicating it is an accepting state or r, indicating rejection. Of the 16 possible states, it turns out that
3、only 13 are accessible from the initial state, 000r. Here is the transition table: 杠杆可能出现8种情况,影响着最终状态。并且也要说明,前面一个大理石球是否从D滚出,也就是说,前一个输入是否被接受。令 0 代表向左方的状态(如图表), 1 代表向右方。这三个杠杆的每一个状态都可以用三个数(0或1)组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态,r代表拒绝状态。16种可能的状态中,只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。 A B-000r 100r 011r*000a 100
4、r 011r*001a 101r 000a010r 110r 001a*010a 110r 001a011r 111r 010a100r 010r 111r*100a 010r 111r101r 011r 100a*101a 011r 100a110r 000a 101a*110a 000a 101a111r 001a 110aExercise 2.2.2The statement to be proved is -hat(q,xy) = -hat(-hat(q,x),y), and we proceed by induction on the length of y. 证明:通过对|y|进行
5、归纳,来证明(q , xy)=(q , x) , y) ,具体过程如下: Basis: If y = , then the statement is -hat(q,x) = -hat(-hat(q,x),). This statement follows from the basis in the definition of -hat. Note that in applying this definition, we must treat -hat(q,x) as if it were just a state, say p. Then, the statement to be proved
6、 is p = -hat(p,), which is easy to recognize as the basis in the definition of -hat. 基础: =0,则y=。那么需证(q,x)=(q ,x),),记p=(q,x),命题变为 p=(p ,), 由的定义知这显然成立。Induction: Assume the statement for strings shorter than y, and break y = za, where a is the last symbol of y. The steps converting -hat(-hat(q,x),y) t
7、o -hat(q,xy) are summarized in the following table: 归纳: 假设命题对于比 y短的串成立, 且y = za, 其中 a 是y的结尾符号。(q,x),y) 到(q,xy) 的变换总结在下表中: Expression 表达式Reason 原因(q,x),y) Start 开始(q,x),za) y=za by assumption 由假设y=za(q,x),z),a) Definition of -hat, treating -hat(q,x) as a state 的定义, 把(q,x) 看作是一个状态(q,xz),a) Inductive h
8、ypothesis 归纳假设(q,xza) Definition of -hat 的定义(q,xy) y=zaExercise 2.2.4(a)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 AB C A*C C AExercise 2.2.6(a)The trick is to realize that reading another bit eith
9、er multiplies the number seen so far by 2 (if it is a 0), or multiplies by 2 and then adds 1 (if it is a 1). We dont need to remember the entire number seen - just its remainder when divided by 5. That is, if we have any number of the form 5a+b, where b is the remainder, between 0 and 4, then 2(5a+b
10、) = 10a+2b. Since 10a is surely divisible by 5, the remainder of 10a+2b is the same as the remainder of 2b when divided by 5. Since b, is 0, 1, 2, 3, or 4, we can tabulate the answers easily. The same idea holds if we want to consider what happens to 5a+b if we multiply by 2 and add 1. 对于一个二进制整数,如果读
11、入一个比特,其值等于原数乘以;否则等于原数乘以再加以1。而任意一个数均可写成形如5a+b,其中a任意,0= b *q0 q0 q1q1 q2 q3q2 q4 q0q3 q1 q2q4 q3 q4There is a small matter, however, that this automaton accepts strings with leading 0s. Since the problem calls for accepting only those strings that begin with 1, we need an additional state s, the start
12、 state, and an additional dead state d. If, in state s, we see a 1 first, we act like q0; i.e., we go to state q1. However, if the first input is 0, we should never accept, so we go to state d, which we never leave. The complete automaton is: 但是上述自动机仍接受以开头的字符串。因为题目要求只接受以开头的串,可增加一个初始状态s和“死亡状态”d。在状态初始
13、状态s, 若看到,则转到状态q1;若看到, 则直接转到状态d,识别终止。所求自动机如下: 0 1-s d q1*q0 q0 q1q1 q2 q3q2 q4 q0q3 q1 q2q4 q3 q4d d dExercise 2.2.9Part (a) is an easy induction on the length of w, starting at length 1. Basis: |w| = 1. Then -hat(q0,w) = -hat(qf,w), because w is a single symbol, and -hat agrees with on single symbol
14、s. Induction: Let w = za, so the inductive hypothesis applies to z. Then -hat(q0,w) = -hat(q0,za) = (-hat(q0,z),a) = (-hat(qf,z),a) by the inductive hypothesis = -hat(qf,za) = -hat(qf,w). 证明:a) 通过对w长度的归纳证明。 基础: 若|w| = 1,则w 是一个符号,此时需证(q0,w) = (qf,w), 而对于单个符号扩展转移函数与转移函数的作用是一样的,得证。 归纳: 令w = za, 假设对于z命题
15、q0,z) = (qf,z)成立。那么(q0,w) = (q0,za) = (q0,z),a) = ( (qf,z),a) 由归纳假设 = (qf,za) = (qf,w). For part (b), we know that -hat(q0,x) = qf. Since x, we know by part (a) that -hat(qf,x) = qf. It is then a simple induction on k to show that -hat(q0,xk) = qf. Basis: For k=1 the statement is given. Induction:
16、Assume the statement for k-1; i.e., -hat(q0,xSUPk-1) = qf. Using Exercise 2.2.2, -hat(q0,xk) = -hat(-hat(q0,xk-1),x) = -hat(qf,x) by the inductive hypothesis = qf by (a). b) x是属于L(A)的非空串,也即串x被接收,因此(q0,x) = qf ,则由 a)知(qf,x) =(q0,x)= qf 。现在通过对k 的归纳来证明(q0,xk) = qf 。基础: k=1 时,需证(q0,x) = qf ,由已知可得。归纳:假设对
17、于k-1命题成立,也就是说,(q0,xk-1) = qf 。由练习 2.2.2, (q0,xk) =(q0,xk-1),x) = (qf,x) 由归纳假设 = qf 由(a)。 Exercise 2.2.10The automaton tells whether the number of 1s seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an
18、even number of 1s. Basis: |w| = 0. Then w, the empty string surely has an even number of 1s, namely zero 1s, and (A,w) = A. Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1. Case 1: a = 0. If w has an even number of 1s, so does z. By the inductive hyp
19、othesis, (A,z) = A. The transitions of the DFA tell us (A,w) = A. If w has an odd number of 1s, then so does z. By the inductive hypothesis, -hat(A,z) = B, and the transitions of the DFA tell us -hat(A,w) = B. Thus, in this case, -hat(A,w) = A if and only if w has an even number of 1s. Case 2: a = 1
20、 If w has an even number of 1s, then z has an odd number of 1s. By the inductive hypothesis, -hat(A,z) = B. The transitions of the DFA tell us -hat(A,w) = A. If w has an odd number of 1s, then z has an even number of 1s. By the inductive hypothesis, -hat(A,z) = A, and the transitions of the DFA tel
21、l us -hat(A,w) = B. Thus, in this case as well, -hat(A,w) = A if and only if w has an even number of 1s. 这个自动机表示,状态A表示偶数个1,状态B表示奇数个1,不管串有偶数个还是奇数个1,都会被接受。当且仅当串w中有偶数个1时, (A,w) = A.。用归纳法证明如下基础: |w| = 0。空串当然有偶数个 1 ,即0个 1,且 (A,w) = A. 归纳:假设对于比w 短的串命题成立。令 w = za, 其中 a 为 0 或1。 情形1: a = 0. 如果w有偶数个 1, 则z有偶数个
22、1。由归纳假设, (A,z) = A。由转移表的DFA知(A,w) = A.如果w有奇数个1, 则z有奇数个1. 由归纳假设, (A,z) = B, 由转移表的 DFA 知 (A,w) = B. 因此这种情况下(A,w) = A 当且仅当 w 有偶数个 1。 情形2: a = 1. 如果w有偶数个 1, 则z有奇数个1。由归纳假设, (A,z) = B. 由转移表的DFA知 (A,w) = A. 如果w有奇数个 1, 则z有偶数个1。由归纳假设, (A,z) = A, 由转移表的DFA知 (A,w) = B. 因此这种情况下(A,w) = A 当且仅当 w 有偶数个 1. 综合上述情形,命题得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 5034657600 自动 机理 论语 言和 计算 导论 课后 习题 答案 中文版
