计算理论答案汇总.docx

第一章 练习 1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题. M1的起始状态是q1 M1的接受状态集是{q2} M2的起始状态是q1 M2的接受状态集是｛q1，q4｝ 对输入aabb,M1经过的状态序列是q1，q2，q3，q1，q1 M1接受字符串aabb吗？否 M2接受字符串ε吗？是 1.2 给出练习2.1中画出的机器M1和M2的形式描述. M1=(Q1,Σ,δ1,q1,F1) 其中 Q1={q1,q2,q3,}; Σ={a,b}; δ1为： a b q1 q2 q3 q2 q1 q3 q3 q2 q1 q1是起始状态 F1={q2} M2=(Q2,Σ,δ2,q2,F2) 其中 Q2={q1,q2,q3,q4}; Σ={a,b}; 3）δ2为： a b q1 q2 q3 q4 q1 q2 q3 q4 q2 q1 q3 q4 q2是起始状态 F2={q1,q4} 1.3 DFA M的形式描述为 ( {q1，q2，q3，q4，q5}，{u,d},δ,q3，{q3}),其中δ在表2-3中给出。试画出此机器的状态图。 q q1 q5 q4 q2 q3 u d u u u u d d d d 1.6 画出识别下述语言的DFA的状态图。 a){w | w从1开始以0结束} 0 0 0 1 1 1 0,1 0 010011 0 1 0 0 1 1 0,1 0,1100 0,1 1 0 0 1 1 0 1 0 0,100,10,111 0,1 0 0,1 0,1 1 1 0,1 0 0,10,10,100,11e) {w | w从 0,1 0,1 0,1 0 0,1 1 0,1 0,1 0 0,1 1 或 0,10101 0,1 0 1 0 1 1 0 0,10,10,10,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 1110,1000h){w | w 1 1 1 0,1 0 0 0 100,10,1 1 0 0,1 0,1 j) {w | w至少含有2个0，且至多含有1个1} 0 0 0 1 0 0 1 1 1 1 1 0 0 0,1 k) {ε,0} 0 0 0,1 0,1 1 110011 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 m) 空集 n) 除空串外的所有字符串 0,10,1 0,1 0,1 0,1 1.7 给出识别下述语言的NFA，且要求符合规定的状态数。 000,1a. {w | w以00结束}，三个状态 0 0 0,1 010,1010,1b. 语言｛w | w含有子串0101，即对某个x和y，w= 0 1 0,1 0 1 0,1 ?011101000?c. 语言｛ ? 0 1 1 1 0 1 0 0 0 ? d. 语言｛0｝，2个状态。 0 0 e. 语言0*1*0*0，3个状态。 ? ? 0 0 1 0 f. 语言{ε}，1个状态。 g. 语言0*，1个状态。 0 0 2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。 证明:设NFA M={Q，Σ,δ,q0,F}，F={ri1，……，rik}.添加一个状态p后，ri1，……，rik分别向p引ε箭头，将ri1，……，rik变为非接受状态，p变为接受状态。又因为添加ε箭头不影响NFA识别语言，所以命题成立。 2.14 a 证明：设M是一台语言B的DFA，交换M的接状态与非接受状态得到一台新的DFA，则这台新的DFA是识别B 的补集，因此，正则语言类受在补运算下封闭。 b 举例说明：设M是一台识别语言B的NFA，交换M的接受状态与非接受状态得到一台新的NFA，这台新的NFA不一定识别B的补集。NFA识别的语言类在补集下封闭吗？解释你的回答。 解： M是DFA, M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串，因为M与N均为DFA,所以必然存在Q中状态序列r0,r1,…,rn,使得：r0=q0, δ(ri, ωi+1)=ri+1, i=0,…,n-1 1)若rn?F 则ω?B; 2)若rn?F,则rn?Q-F,即N接受ω，若ω?B, 所以N接受B的补集，即B的补集正则。 所以，正则语言类在补运算下封闭。 0 0 设B为{0}。NFA M： 0可识别它。 0 依题对它作变换，得到N： 则N识别的语言{ε}不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。 但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补