http://www.zhiwenweb.cn/article.asp?id=122 6
Solutions for Section 2.2
Exercise 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
the right. Each state can be represented by a sequence of three 0's or 1's, 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 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 100r 011r
*001a 101r 000a
010r 110r 001a
*010a 110r 001a
011r 111r 010a
100r 010r 111r
*100a 010r 111r
101r 011r 100a
*101a 011r 100a
110r 000a 101a
*110a 000a 101a
111r 001a 110a
Exercise 2.2.2
The statement to be proved is δ-hat(q,xy) = δ-hat(δ-hat(q,x),y), and we proceed by
induction on the length of y.
证明：通过对|y|进行归纳，来证明 (q , xy)= ( (q , x) , y) ，具体过程如下：
志文工作室
1
剩余63页未读，继续阅读
- 1
- 2
- 3
前往页