内容发布更新时间 : 2024/11/19 21:41:24星期一 下面是文章的全部内容请认真阅读。

第一章

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为：

q1 q2 q3 a b q2 q1 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为：

q1 q2 q3 q4 a b q1 q2 q3 q4 q2 q1 q3 q4 3）q2是起始状态

4）F2={q1,q4}

1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。 u

1.6 画出识别下述语言的DFA的状态图。

a){w | w从1开始以0结束}

1

1 1

0 0 0,1 q1 u d q2 u d q3 u d q4 u d q5 d

0

b){w | w至少有3个1}

c) {w | w含有子串0101}

1 d) {w | w的长度不小于3，且第三个符号为0}

0,1 0,1 1 0,1 0 1 0 0,1 1 0 0 1 0 0 1 0,1 0 1 0 1 0 1 0,1 e) {w | w从0开始且为奇长度，或从1开始且为偶长度}

0 1 0,1 0,1 0,1 0,1 f) {w | w不含子串110}

0

1

0 g) {w | w的长度不超过5}

0,1 0,1 0,1 0,1 0,1 0,1 0,1 1 1 0 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 0,1 0,1 j) {w | w至少含有2个0，且至多含有1个1}

1 0 1 0 1 0 k) {ε,0}

0 1 0 0,1 0,1 0 0 1 1 1 0,1