1.1 图给出两台DFA M1和M2的状态图. 回答下述囿关问题.

d. M2的接受状态集是｛q1q4｝

1.2 给出练习2.1中画出的机器M1和M2的形式描述.

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

0,1 0,1 1.7 给出识别下述语言状态是什么的NFA且要求符合规定的状态数。 a. {w | w以00结束}三个状态

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

d. 语言状态是什么｛0｝，2个状態

f. 语言状态是什么{ε}，1个状态

g. 语言状态是什么0*，1个状态

0 1.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。

证明:设NFA M={QΣ,δ,q0,F}，F={ri1??，rik}.添加一个状态p后ri1，??rik分别向p引ε箭头，将ri1，??rik变为非接受状态，p变为接受状态又因为添加ε箭头不影响NFA识别语言状态是什么，所以命題成立

1.14 a 证明：设M是一台语言状态是什么B的DFA，交换M的接状态与非接受状态得到一台新的DFA

则这台新的DFA是识别B 的补集，因此正则语言状态昰什么类受在补运算下封闭。 b 举例说明：设M是一台识别语言状态是什么B的NFA交换M的接受状态与非接受状态得到一台新的NFA，这台新的NFA不一定識别B的补集NFA识别的语言状态是什么类在补集下封闭吗？解释你的回答 解：

2)若rn?F,则rn?Q-F,即N接受ω，若ω?B, 所以N接受B的补集，即B的补集正则 所以，正则语言状态是什么类在补运算下封闭

依题对它作变换，得到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即正则语言状态是什么类在星号运算下封闭。