计 算 理 论--------老师说这是一本大书，我要彻底理解她！
练习
1.1 图给出两台 DFA M
1
和 M
2
的状态图. 回答下述有关问题.
a. M
1
的起始状态是 q
1
b. M
1
的接受状态集是{q
2
}
c. M
2
的起始状态是 q
1
d. M
2
的接受状态集是｛q
1
，q
4
｝
e. 对输入 aabb,M
1
经过的状态序列是 q
1
，q
2
，q
3
，q
1
，q
1
f. M
1
接受字符串 aabb 吗？否
g. M
2
接受字符串 ε 吗？是
1.2 给出练习 2.1 中画出的机器 M
1
和 M
2
的形式描述.
M
1
=(Q
1
,Σ,δ
1
,q
1
,F
1
) 其中
1）Q
1
={q
1
,q
2
,q
3
,};
2）Σ={a,b};
3）δ
1
为：
a b
q
1
q
2
q
3
q
2
q
1
q
3
q
3
q
2
q
1
4）q
1
是起始状态
5）F
1
={q
2
}
M
2
=(Q
2
,Σ,δ
2
,q
2
,F
2
) 其中
1）Q
2
={q
1
,q
2
,q
3
,q
4
};
2）Σ={a,b};
3）δ
2
为：
a b
q
1
q
2
q
3
q
4
q
1
q
2
q
3
q
4
q
2
q
1
q
3
q
4
3）q
2
是起始状态
4）F
2
={q
1
,q
4
}
1.3 DFA M 的形式描述为 ( {q
1
，q
2
，q
3
，q
4
，q
5
}，{u,d},δ,q
3
，{q
3
}),其中 δ 在表
2-3 中给出。试画出此机器的状态图。
1
q
1
q
5
q
4
q
2
q
3
u
d
u u u u
d
dd
d
- 1
- 2
- 3
- 4
- 5
- 6
前往页