计算理论答案汇总.docx

第一章练****图给出两台 DFA M 1和M . 1的起始状态是 q 1的接受状态集是{q 2} 2的起始状态是 q 2的接受状态集是{ q 1,q 4} aabb, M 1经过的状态序列是 q 1,q 2,q 3,q 1,q 1 1接受字符串 aabb 吗?否 2接受字符串ε吗?是 给出练****中画出的机器 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为: abq 1q 2q 3q 2q 1q 3q 3q 2q 14) 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为: abq 1q 2q 3q 4q 1q 2q 3q 4q 2q 1q 3q 43)q 2是起始状态 4)F 2 ={q 1,q 4} DFA M 的形式描述为({q 1,q 2,q 3,q 4,q 5},{u,d },δ,q 3,{q 3 }), 其中δ在表 2-3 中给出。试画出此机器的状态图。 画出识别下述语言的 DFA 的状态图。 a){w |w从1开始以 0结束} q 1q 5q 4q 2q 3 u d uuuu d dd d b){w |w至少有 3个1} c) {w |w含有子串 0101} d) {w |w的长度不小于 3,且第三个符号为 0} e) {w |w从0开始且为奇长度,或从 1开始且为偶长度}或 f){w|w不含子串 110} g) {w |w的长度不超过 5} 00 1110,1 001 0 011 0,1 0,1 1 00 1101 00,1 00,10,1 1 10,1 00,1 0,1 0,1 00,1 1 0,1 00,1 10,1 0 1 0110 0,1 0,1 0,1 0,1 0,1 0,1 0,1 h){w |w是除 11和 111 以外的任何字符} i){w |w的奇位置均为 1} j) {w |w至少含有 2个0,且至多含有 1个1} k){ε,0} l) {w |w含有偶数个 0,或恰好两个 1} m) 空集 n)除空串外的所有字符串 给出识别下述语言的 NFA ,且要求符合规定的状态数。 a. {w |w以00结束},三个状态 { w|w含有子串 0101 ,即对某个 x和y, w= x0101y },5个状态. 1110,1 00000 100 11 11 10 0 0,1 00,10,1 1 10 0,1 0,1 11 00 11 111 00 00 00 1 0,10,1 0,1 00 0,1 01 0,101 0,1 { w|w含有偶数个 0或恰好两个 1},6个状态。 { 0},2个状态。 0 *1 *0 *0,3个状态。 {ε},1个状态。 0 *,1个状态。 证明每一台 NFA 都能够转换成等价的只有一个接受状态的 NFA 。证明:设 NFA M={Q ,Σ,δ,q 0, F}, F={ r i1 ,……,r ik}. 添加一个状态 p后, r i1 ,……,r ik分别向 p引ε箭头, 将r i1 ,……,r ik 变为非接受状态, p 变为接受状态。又因为添加ε箭头不影响 NFA 识别语言,所以命题成立。 a证明:设M是一台语言 B的 DFA ,交换 M 的接状态与非接受状态得到一台新的 DFA ,则这台新的 DFA 是识别 B的补集,因此,正则语言类受在补运算下封闭。 b举例说明:设M是一台识别语言 B的 NFA ,交换 M 的接受状态与非接受状态得到一台新的 NFA ,这台新的 NFA 不一定识别 B的补集。 NFA 识别的语言类在补集下封闭吗?解释你的回答。解: DFA, M是{ Q,∑,δ,q 0 ,F}, 令 N={Q, ∑,δ,q 0 ,Q-F}, 设ω=ω 1ω 2…ω n 是字母表上任意字符串, 因为 M与N 均为 DFA, 所以必然存在 Q 中状态序列 r 0,r 1,…,r n, 使得: r 0 =q 0,δ(r i,ω i+1 )=r i+1, i=0 ,…, n-1 1)若r n?F则ω?B;2)若r n? F,则r n? Q-F, 即N接受ω,若ω? B, 所以 N接受 B的补集,即 B的补集正则。所以,正则语言类在补运算下封闭。 {0} 。 NFA M: 可识别它。依题对它作变换,得到 N