形式语言与自动机理论试题(3)

综上所述，原式得证

*******************************************************************************

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中的状态

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库形式语言与自动机理论试题(3)在线全文阅读。