第一次作业（如有疑问或发现有问题的答案，请联系lsj-5212@stu.xjtu.edu.cn，刘淞佳，西一A段410）

P35 习题2.1.1 图2-8中时一个滚大理石球玩具，在A或B处扔下一个大理石球。杠杆x1、x2和x3让大理石球落向左方或右方。每当一个大理石球遇到一个杠杆时，就引起这个杠杆在大理石球通过之后改变方向，所以下一个大理石球会走相反的分支。 a）用有穷自动机为这个玩具建模。设输入A和B表示扔进大理石球的入口。设接受对应于大理石球从D出来，不接受则表示大理石球从C出来。

A B b）非形式化地描述这个自动机的语言。

→000r 100r 011r

*000a 100r 011r 答案

001r a）状态用四位表示，

*001a 101r 000a 前三位用x1x2x3表示杠杆的方向，0向左，1向右，

010r 110r 001a 第四位用a和r表示，

*010a 110r 001a a表示前一个输入后结果为拒绝，

011r 111r 010a r表示前一个输入后结果为接受。

*011a 右边为转移表

100r 010r 111r

*100a 010r 111r b)这个语言是包含最后一个输出结果为D的所有投入A和B的 球

101r 011r 100a 的串。

*101a 011r 100a

P36 习题2.2.4 给出接受下列在字母表{0,1}上的语言的DFA：

A）所有以00结尾的串的集合。

B）所有带3个连续的0（不必在结尾）的串的集合。 C）带011字串的串的集合。

答案。

a）可以用转移图或者转移表。转移表如下所示。

→A B * C b）

→A B C * D c）

→A B C * D 0 B C D D 1 A A A D

0 B B B D 1 A C D D

0 B C C 1 A A A

110r *110a 111r *111a 000a 000a 001a 101a 101a 110a P36 习题2.2.10 考虑带下列转移表的DFA:

0 1 非形式化地描述这个DFA接受的语言，通过对输入串的长度

→A A B 进行归纳，证明这个描述是正确的。

* B B A 提示：当建立归纳假设时，断言什么样的输入导致每个状态，

而不只是断言什么样的输入导致接受状态，这样更明智些。 答案

这个自动机表示：状态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有偶数个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. 综合上述情形，命题得证。

P45 习题2.3.4 给出接受下列语言的非确定型有穷自动机。尝试尽可能多利用非确定性。 a）在字母表{0,1,...,9}上的串的集合，使得结尾数字在前面出现过。

c）0和1的串的集合，使得有两个0间隔的位置数是4的倍数。注意，0算是4的倍数。 答案

a) qs为初始状态，qf为终止状态，可一直停与qs，即尚未猜测。转移表/图如下所示。 记qi为已看到i并猜测i是结尾将要重复的数字，i=0,1,…,9。

q0 q1 ... q9 * qs c)

→qs q0 q1 q2 q3 q4 * qf

0 {q0} {qf} {q0,q2} {q0,q3} {q0,q4} {qf} {qf} 1 {qs} {q1} {q2} {q3} {q4} {q1} {qf}

0 {qf} {q1} ... {q9} {} 1 {q0} {qf} ... {q9} {} ... ... ... ... ... ... ... 9 {qs,q9} {q0} {q1} ... {qf} {}

→qs {qs,q0} {qs,q1}