1 第2 章、正则语言习题解答 - 练习 2.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 接受字符串ε吗？是 2.2、给出练习2.1 中画出的机器M1 和M2 的形式描述. M1=(Q1,∑,δ1,q1,F1) 其中Q1={q1,q2,q3,}；Σ={a,b}；q1 是起始状态； F1={q2}；δ1 为： a b q1 q2 q3 q2 q1 q3 q3 q2 q1 M2=(Q2,Σ,δ2,q2,F2) 其中Q2={q1,q2,q3,q4}；Σ={a,b}；q2 是起始状态；F2={q1,q4}；δ2 为： a b q1 q2 q3 q4 q1 q2 q3 q4 q2 q1 q3 q4 2.3、DFA M 的形式描述为 ( {q 1，q2，q3，q4，q5}，{u,d}, δ,q3，{q3}),其中δ在表 2-3 中给出。试画出此机器的状态图。 q1 q5 q4 q2 q3 u d u u u u d d d d 2 2.4、画出识别下述语言的 DFA 的状态图。 a) {w | w 从 1 开始以 0 结束} b) {w | w 至少有 3 个 1} c) {w | w 含有子串 0101} d) {w | w 的长度不小于 3，且第三个符号为 0} e) {w | w 从 0 开始且为奇长度，或从 1 开始且为偶长度} 或 f) {w | w 不含子串 110} 0 0 1 1 1 0,1 0 0 1 0 0 1 1 0,1 0,1 1 0 0 1 1 0 1 0 0,1 0,1 0,1 1 0,1 0 0,1 0,1 0,1 0 0,1 1 0,1 0 0,1 1 0,1 0 1 0 1 1 0 3 g) {w | w 的长度不超过5} h){w | w 是除11 和111 以外的任何字符串} i){w | w 的奇位置均为1} j) {w | w 至少含有2 个0，且至多含有1 个1} k) {ε,0} l) {w | w 含有偶数个0，或恰好两个1} ，和下一题c)作一比较。 m) 空集 0 0,1 0,1 1 1 0 0,1 0,1 0,1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 含有偶数个0，任意个1。 注意：偶数包括 0。 含有奇数个0，恰好两个1。 1 1 1 0 0,10 0 0,1 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 4 n) 除空串外的所有字符串 2.5、给出识别下述语言的NFA，且要求符合规定的状态数。 a. {w | w 以00 结束} ，三个状态 b. 语言｛w | w 含有子串0101，即对某个x 和y，w=x0101y｝，5 个状态. c....
