发布时间 : 星期三 文章计算理论习题答案CHAP1newedit更新完毕开始阅读8662752b915f804d2b16c1a6
练习
1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.
a. M1的起始状态是q1 b. M1的接受状态集是{q2} c. M2的起始状态是q1
d. M2的接受状态集是｛q1，q4｝
e. 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1 f. M1接受字符串aabb吗？否 g. M2接受字符串ε吗？是
1.2 给出练习2.1中画出的机器M1和M2的形式描述.
M1=(Q1,Σ,δ1,q1,F1) 其中 1）Q1={q1,q2,q3,}; 2）Σ={a,b}; 3）δ1为： a b q1 q2 q1 q2 q3 q3 q3 q2 q1 4）q1是起始状态 5）F1={q2}
M2=(Q2,Σ,δ2,q2,F2) 其中 1）Q2={q1,q2,q3,q4}; 2）Σ={a,b}; 3）δ2为： a b q1 q1 q2 q2 q3 q4 q3 q2 q1 q4 q3 q4 3）q2是起始状态 4）F2={q1,q4}
1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。
d d d d u q1 q2 q3 d q4 q5 u u u u
1.6 画出识别下述语言的DFA的状态图。
a){w | w从1开始以0结束}
1
1 1 0
0 0
0,1
b){w | w至少有3个1}
0 0 0 0,1
1 1 1
c) {w | w含有子串0101} 1 0,1 0 0 0 1 0 1
1
d) {w | w的长度不小于3，且第三个符号为0}
1 0,1 0
0,1 0,1 0
1 0,1
e) {w | w从0开始且为奇长度，或从1开始且为偶长度}
0,1
0 0 或 0,1 0,1 0,1 1 1
0,1
0,1 1 0
0 5} g) {w | w的长度不超过
0,1 0,1 0,1 0,1 0,1
h){w | w是除11和111以外的任何字符}
1 1 1
0 0 0 0,1
i){w | w的奇位置均为1}
1
0,1 0
0,1
j) {w | w至少含有2个0，且至多含有1个1} 1
1
0 0
1 1 0,1
1 0 0
1
0 0
k) {ε,0} 0 0,1 0,1
1
l) {w | w含有偶数个0，或恰好两个1}
1 1 1
1
0 0 0 0 0 0 0 0 1 1 1 1 f) {w | w不含子串110}
0
1 1 0,1 0,1 0,1
m) 空集 n) 除空串外的所有字符串 0,1 0,1 0,1
1.7 给出识别下述语言的NFA，且要求符合规定的状态数。
a. {w | w以00结束}，三个状态 0,1
0 0
b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.
0,1 0,1
0 1 0 1
c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。
1 1 0
? 0 0 0 0
? 1 1
d. 语言｛0｝，2个状态。
0
e. 语言0*1*0*0，3个状态。
0 1 0
? 0
f. 语言{ε}，1个状态。
g. 语言0*，1个状态。
0
2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。
证明:设NFA M={Q，Σ,δ,q0,F}，F={ri1，??，rik}.添加一个状态p后，ri1，??，
rik分别向p引ε箭头，将ri1，??，rik变为非接受状态，p变为接受状态。又因为添