计算理论习题解答

计算理论习题解答

练习

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 4） F2={q1,q4}

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

d d d d u q1 q2 q3 d q4 q5 u u u u

- 1 -

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

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

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

1 1 1 0

0 0 0,1

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

0 0 0 0,1

1 1 1

c) {w | w含有子串0101} 1 0 0,1 0 0 1 0 1

1

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

1 0 0,1

0,1 0,1 0

1 0,1

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

0,1 开始且为偶长度}

0 0,1 或 0 0,1 0,1

1 0,1 1

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

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

0,1 0,1 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 0 1 1 1 0,1

0 0 1 1

0 0 k) {ε,0} 0

0,1 0,1

1 l) {w | w含有偶数个0，或恰好两个1}

1 1 1

1 0 0 0 0 0 0 0 0 1 1 1

1 m) 空集 n) 除空串外的所有字符串

0,1 0,1 0,1 给出识别下述语言的NFA，且要求符合规定的状态数。

- 3 -

1.7

a. {w | w以00结束}，三个状态 0,1

0 0

b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.

g. 语言0*，1个状态。

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识别的语言类在补集下封闭吗？解释你的回答。 解：

a. M是DFA, M是{Q,∑,δ,q0,F},令N={Q,∑,δ,q0,Q-F},设ω=ω1ω2…ωn是字母表上任意字符串，

- 4 -

0,1 0 1 0 1 0,1 c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。

1 0 ? 0 ? d. 语言｛0｝，2个状态。

1 0 0 1 1 0 0 e. 语言0*1*0*0，3个状态。

0 ? f. 语言{ε}，1个状态。

1 0 0

因为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 b. 设B为{0}。NFA M：

可识别它。

0 依题对它作变换，得到N：

则N识别的语言{ε}不是B的子集。所以交换M的接受状态与非接受状态得到的新的NFA不一定识别B的补集。

但是由于NFA识别的语言类与DFA识别的语言类相同，即正则语言类。由a的证明，正则语言类在补运算封闭，可知，NFA识别的语言类---正则语言类在补运算下封闭。

若NFA识别语言A，必有 等价的DFA识别A,从而由a知，可交换DFA的接受与非接受状态构造识别A的补集的DFA,则必有等价的NFA识别A的补集。只是，该NFA未必有原NFA交换接受与非接受状态构造而成。

1.15 给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。设N=（Q1,Σ,δ

。N应该识别A1*。 1,q1,F1）识别A1。如下构造N=（Q1,Σ,δ1,q1,F1）

a. N的状态集是N1的状态集。

b. N的起始状态是N1的起始状态相同。

c. F=｛q1｝∪F1。F的接受状态是原来的接受状态加上它的起始状态。

d. 定义δ如下：对每一个q属于Q和每一个a属于Σ。

??1(q,a), 若q?F1 或 a???(q,a)????1(q,a)?{q1}, 若q?F1 且 a??

解：设N1识别语言A={至少含有一个1}，其中输入字母表为{0，1}，可知A*={空串或至少含有一个1}。 a 0,1 0,1 N1: N:

a,b 1 1 2 b ?

按上述规定构造N的状态图如上。可以看出L(N)={0,1}*不等于A*. 所以如此构造的N不一定识别A*.

1.16 使用定理2.19中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。

0,1 0,1 ? 1 1 2 a)， b)， a a a,b 3 b - 5 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算理论习题解答在线全文阅读。