第3章 作业及参考答案.doc

1、针对DFA M1，
(1)请给出在处理字符串1011001的过程中经过的状态序列。
解：经过的状态序列为：q0q3q1q3q2q3q1q3
(2)请给出形式描述。
争议：M1的形式化还是接受过程的形式化？
解：M1的形式描述为M1=({q0,q1,q2,q3},{0,1},δ, q0,{ q3})
其中δ定义为：
δ(q0,0)= q1，δ(q0,1)= q3
δ(q1,0)= q2，δ(q1,1)= q3
δ(q2,0)= q3，δ(q2,1)= q0
δ(q3,0)= q1，δ(q3,1)= q2
接受过程的形式化：q01011001├1q3011001├10q111001├101q31001├1011q2001├10110q301├101100q11├1011001q3
注意：谈及自动机形式化描述，一定是用五元组表示，将δ函数直接写出来
2、构造识别下列语言的DFA
（要求写出形式化描述，另外，写出设计过程对理清你的思维更有益）
(3) {x| x∈{0,1}+且x中不含形如00的子串}
1
0
0
1
qt
qs
q1
S
1
0,1
q0
0

或：(对, 但稍嫌麻烦)
1
0
1
0
0
1
qt
qs
q1
S
1
q0
0
q２
　------------05级孙磊
错解:
1
0
q0
S
q1
q2
1
0
0,1
1
0
q0
S
q1
q3
1
0
0,1
q2
0,1
0
(x∈{0,1}*)
1
0
q0
S
q1
1
0
(不接受1, 可接受000)
(5) {x| x∈{0,1}+且x中含形如10110的子串}
1
1
q0
S
q1
q2
q3
q4
q5
0
0
1
1
0
0
0
1
0,1

q0：起始状态，以及未读入1的状态；
q1：读入了10110中第1个符号(1)的状态；
q2：读入了10110中第2个符号(0)的状态；
q3：读入了10110中第3个符号(1)的状态；
q4：读入了10110中第4个符号(1)的状态；
q5：读入了10110中第5个符号(0)的状态；

易犯的错误: 状态转移时, 不考虑已接受一些字符后所处状态, 一味地转到开始状态，不利用阶段性成果，狗熊掰棒子！
1
1
q0
S
q1
q2
q3
q4
q5
0
0
1
1
0
0
0
0,1
1

(7) {x| x∈{0,1}+且把x看成二进制数时，x模5与3同余，要求中当x为0时，|x|=1，且x≠0时，x首字符是1}
提示: 和P98例3-5属同一类型, 这种设计如不写清楚设计过程, 不能服人, 也不能反映你的设计方法.
解：按题意，当x为0时，x的长度为1，即不能出现多于1个0的全0串；当x不为0时，必须以1开始。又由于0模5与3不同余，故在开始状态qs读入0，则直接进入陷阱状态qt，即δ(qs,0)= qt。其余状态为：
q1：对应x模5与1同余的等价类；
q2：对应x模5与2同余的等价类；
q3：对应x模5与3同余的等价类(终止状态)；
q4：对应x模5与4同余的等价类；
q5：对应x模5与0同余的等价类(x≠0)；
所以，要构造的DFA为：M=({qs,q1,q2,q3,q4,q5,qt},{0,1},δ, qs,{ q3})
状态转换函数δ定义如下：
(0)在初始状态qs，δ(qs,0)= qt，δ(qs,1)= q1
(1)当处于q1状态时，已读入的x=5n+1, n≥0
由2x+0=5×2n+2，有δ(q1,0)= q2
由2x+1=5×2n+3，有δ(q1,1)= q3
(2)当处于q2状态时，已读入的x=5n+2, n≥0
由2x+0=5×2n+4，有δ(q2,0)= q4
由2x+1=5×(2n+1)+0，有δ(q2,1)= q5
(3)当处于q3状态时，已读入的x=5n+3, n≥0
由2x+0=5×(2n+1)+1，有δ(q3,0)= q1
由2x+1=5×(2n+1)+2，有δ(q3,1)= q2
(4)当处于q4状态时，已读入的x=5n+4, n≥0
由2x+0=5×(2n+1)+3，有δ(q4,0)= q3
由2x+1=5×(2n+2)+4，有δ(q4,1)= q4
(5)当处于q5状态时，已读入的x=5n, n>1
由2x+0=5×2n+0，有δ(q5,0)= q5
由2x+1=5×2n+1，有δ(q5,1)= q1
(6)在陷阱状态qt，有δ(qt,0)= qt，δ(qt,1)= qt
1
q2
0
1
qs
S
q1
q4
q3
0
0
0
1
1
1
1
0
q5
qt
0,1
0

(10) {x| x∈{0,1}+且x中至少含两个1 }
0
1
q0
S
q1
q2
0
1
0,1

或
0
0
1
S
0
1
0,1
1
------05级张士光
错解:
0
1
q0
S
q1
q2
0
1
0,1
------错误原因?
10、构造识别下列语言的NFA
(要求写出形式化描述)
(2) {x| x∈{0,1}+且x中含形如10110的子串}
1
q0
S
q1
q2
q3
q4
q5
0,1
0
1
1
0
0,1

错解:
1
q0
S
q1
q2
q3
q4
q5
0
1
1
0
0,1
qt
0,1
0
0
0
1
1
-----用的是DFA思维
另一不能算错的错误: 设计DFA

形式化描述时易犯的错误: δ(q3,1)= q2 或δ(q3,1)={ q2}

(8) {x| x∈{0,1}+且x的首字符和尾字符相同}
1
1
q1
q0
S
q2
q3
0,1
0
0
0,1
q4

或
1
1
q1
q0
S
q2
q3
0,1
0
0
0,1

或(后面的这两个解更好!严格讲, 前两解不全对)
1
1
q1
q0
S
q2
q3
0,1
0
0
0,1
q4
0,1
--------05级孙亮波
或
1
1
q1
q0
S
q2
q3
0,1
0
0
0,1
0,1
--------05级孙磊

11(1)、根据给定的NFA，构造与之等价的DFA
状态说明
状态
输入字符
0
1
2
开始状态
[q0]
q0 q1
[q0 q2]
[q0 q2]

[q0 q1]
[q0 q1 q3]
[q0 q2]
[q0 q2]

[q0 q2]
[q0 q1]
[q0 q1 q2 q3]
[q0 q1 q2]
终止状态
[q0 q1 q3]
[q0 q1 q2 q3]
[q0 q2 q3]
[q0 q2]

[q0 q1 q2]
[q0 q1 q3]
[q0 q1 q2 q3]
[q0 q1 q2]
终止状态
[q0 q2 q3]
[q0 q1 q2 q3]
[q0 q1 q2 q3]
[q0 q1 q2]
终止状态
[q0 q1 q2 q3]
[q0 q1 q2 q3]
[q0 q1 q2 q3]
[q0 q1 q2]
形式化描述与状态转移图略.

不合适的解法:
(1)专门列出一个产生式S®q0
(2)列出2Q中所有状态组, 没有必要; (2)状态组不用[ ]括起来, 虽然本质上没有问题, 但可能忽略”状态集-状态组-单个状态”在思维上的转变.

20、构造图3-20所给DFA对应的右线性文法（做左图）
解：
q0®0q1|1q3|1
q1®0q0|1q3|1
q3®0q1|1q1
q2®0q3|1q1|0
补充: 先将无用状态q2去掉再做 ----05级张志辉, 岳宝提出
不合适的解法: 把非终结符qi(原自动机中的状态)换为S,A,B等在文法中常见的符号, 抽象是去除表面的现象, 保留其实质所在, 如果在用的符号上都得费心思变一下才行, 对抽象能力培养不利(我以这个理由辩不该换符号, 其实你也可以同样的理由辩换了也无所谓, 但我觉得还是不换为好.)

22(1)、根据下列所给文法，构造相应的FA
G1：S®a|aA
A®a|aA|cA|bB
B®a|b|c|aB|bB|cB
解：FA M=({S,A,B,Z}, {a,b,c},d, S, {Z})，其中δ为
d (S,a)= {Z,A}
d (A,a)= {Z,A}
d (A,c)= { A}
d (A,b)= {B}
d (B,a)= {Z,B}
d (B,b)= {Z,B}
d (B,c)= {Z,B}
(可以画出状态转移图)
不合适的解法: 同20题, 换符号
错误写法：
由A®a，δ(A,a)= {Z}
由A®a，δ(A,a)= Z
由A®aA，δ(A,a)= {A}
由A®aA，δ(A,a)= A
应该是：由A®a，ZÎd(A,a)
由A®aA，AÎd(A,a)