综上所述，原式得证
*******************************************************************************
8．证明:对于任意的DFA M1=(Q,Σ,δ,q0,F1) 存在DFA M2=(Q,Σ,δ,q0,F2), 使得L(M2)=Σ*—L（M1）。 证明：（1）构造M2。 设DFA M1=(Q,Σ,δ,q0,F1) 取DFA M2=(Q,Σ,δ,q0,Q—F1) （2）证明L(M2)=Σ*—L（M1）
对任意x?Σ*
x? L(M2)=Σ*—L（M1）?δ(q,x)?Q—F1?δ（q,x）?Q并且δ（q,x）?F1?x?Σ*并且
x?L(M1)?x?Σ*—L（M1）
10、构造识别下列语言的NFA
(1){xx?{0,1}且x中不含形如00的子串}
1?S010111 (2){xx?{0,1}且x中含形如10110的子串}
?10110，100，1
(3){xx?{0,1}且x中不含形如10110的子串}
?10110，100，1
(4){xx?{0,1}和x的倒数第10个字符是1，且以01结尾}
?
0，10，10，10，110，1100，10，10，1
(5){xx?{0,1}且x以0开头以1结尾}
0，1?01
(6){xx?{0,1}且x中至少含有两个1}
0，10，10，1?S110，1
(7){xx?{0,1}且如果x以1结尾，则它的长度为偶数；*
如果以0结尾，则它的长度为奇数}1S00，1 (8){xx?{0,1}且x的首字符和尾字符相等}
00，1?00110，11
(9){x?xTx,??{0,1}}
0,1?00110,1 11.根据给定的NFA，构造与之等价的DFA. （1） NFA M1 的状态转移函数如表3-9 状态说明 状态 0 开始状态 输入字符 1 {q0,q2} 2 {q0,q2} {q2} q0 q1 q2 q3 状态 {q0,q1} {q3,q0} ? ?{q3,q1} {q2,q1} { q0} 终止状态 解答： 状态说明 {q3,q2} {q3 } 输入字符 0 开始状态 1 [q0,q2] [q0,q2] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0, q2,q3] [q0,q1,q2,q3] 2 [q0,q2] [q0,q2] [q0,q1,q2] [q0,q1,q2] [q0,q1,q2] [q0, q2] q0 [q0,q1] [q0,q2] [q0,q1,q2] [q0,q1,q3] [q0,q2,q3] [q0,q1] [q0,q1,q3] [q0,q1] [q0,q1,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] 终止状态 终止状态 终止状态 [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2]
q0[q0,q1][q0,q1,q3][q0,q2,q3]0011,201,22[q0,q1,q2]2120,1[q0,q1,q2,q3]2
00,1[q0,q2]图3-9所示NFA等价的DFA 13．试给出一个构造方法，对于任意的NFA M1?(Q1,?,?1,q0,F1)，构造NFA M2?(Q2,?,?2,q0,F2)，使得L(M2)??*?L(M1)
注：转化成相应的DFA进行处理，然后可参考第8题的思路
证明：
M3根据定理3.1L(M3)?L(M1) 首先构造一个与NFA M1等价的DFA ，（P106），
构造M3?(Q3,?,?3,[q0],F3),其中
Q3?2Q1,F3?{[p1,p2...pm]|{p1,p2...pm}?Q,{p1,p2...pm}?F1??},{p1,p2...pm}?Q,a???3([q1...qn],a)?[p1...pm]??1({q1...qn},a)?{p1...pm}
在此基础上M2，Q2?Q3,?2??3,F2?{[p1...pm]|[p1...pm]?F3??} 即取所有M1确定化后不是终结状态的状态为M2的终结状态。 为了证明L(M2)??*?L(M3)，我们在M3的基础上M4其?(Q4,?,?4,q0,F4)，
中Q4?Q3,?4??3,F4?Q4，即所有M1确定化后的状态都为终结状态。显然L(M4)??*,
??(q0,x)?F3???x?L(M3),又因为
?x?L(M2),则?(q0,x)?F2???(q0,x)?Q3??(q0,x)?F4??(q0,x)?L(M4)??*,故x??*?L(M3)，
故L(M2)??*?L(M3)
同理容易证明L(M2)?故L(M2)??*?L(M3)
?*?L(M3)，又因为L(M3)?L(M1)，故L(M2)??*?L(M1)
可知，构造的M2是符合要求的。
15．P129 15.(1)、（2）
（1）根据NFAM3的状态转移函数，起始状态q0的?闭包为 ?-CLOSURE（q0）={ q0, q2}。由此对以后每输入一个字符后得到的新状态再做?闭包，得到下表： （陶文婧 02282085） 状态 { q0, q2} { q0, q1，q2} { q0, q1，q2，q3} 0 { q0, q1，q2} { q0, q1，q2，q3} { q0, q1，q2，q3} 1 { q0, q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} q0={ q0, q2}，q1={ q0, q1，q2}，q2={ q0, q1，q2，q3}，因为q3为终止状态，所以q2={ q0, q1，q2，q3}为终止状态
0，100，1Sq0q1q2
（2）用上述方法得 状态 { q1, q3} { q3，q2} { q0, q1，q2，q3} { q0, q1，q3} { q1，q2，q3} 0 { q3，q2} { q3，q2} { q1，q2，q3} { q1，q2，q3} { q3，q2} 1 { q0, q1，q2，q3} { q0, q1，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} { q0, q1，q2，q3} q0={ q1, q3}，q1={ q3，q2}，q2={ q0, q1，q2，q3}，q3={ q0, q1，q3}，q4={ q1，q2，q3}因为各状态均含有终止状态，所以q0, q1，q2，q3,q4均为终止状态
11Sq00011q20q1q30q4
注：本题没有必要按照NFA到DFA转化的方法来做，而且从?-NFA到NFA转化时状态没有必要改变，可以完全采用?-NFA中的状态