有限自動(dòng)機(jī)三章答案

1、第三章*1構(gòu)造下列語(yǔ)言的 DFA( 陶文婧 02282085 )（1）0，1 *0，1（ 2）0，1 +S0 ，10 ， 1（3） x|x 0 ，1 +且 x 中不含（設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有00的串00 的子串，就進(jìn)入陷阱狀態(tài)）11S010,100（4） x|x0 ， 1 * 且 x 中不含 00 的串 （可接受空字符串，所以初始狀態(tài)也是接受狀態(tài)）11S0010,10（5） x|x0 ，1 +且 x 中含形如10110 的子串 010,1S10110001（6） x|x0 ，1 +且 x 中不含形如10110 的子串 （設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)有00 的子串，就進(jìn)入陷阱狀態(tài)）1010,

2、1S,1011000（7） x|x0 ，1 +且當(dāng)把 x 看成二進(jìn)制時(shí)， x 模 5和 3同余，要求當(dāng)x 為 0 時(shí)， |x|=1,且x0 時(shí)， x 的首字符為1 1.以 0 開(kāi)頭的串不被接受，故設(shè)置陷阱狀態(tài)，當(dāng)入陷阱狀態(tài)DFA在啟動(dòng)狀態(tài)讀入的符號(hào)為0，則進(jìn)2. 設(shè)置 7 個(gè)狀態(tài)： 開(kāi)始狀態(tài) qs,q0:除以 5 余 0 的等價(jià)類， q1： 除以 5 余 1 的等價(jià)類 ,q2:除以 5余 2 的等價(jià)類， q3:除以 5 余 3 的等價(jià)類， q4:除以 5 余 4 的等價(jià)類，接受狀態(tài)qt3. 狀態(tài)轉(zhuǎn)移表為狀態(tài)01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4q 0011q s0q

3、1q 2q 411100010q tq 30,1（ 8） x|x0 ， 1 +且 x 的第十個(gè)字符為 1（設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x 的第十個(gè)字符為0，進(jìn)入陷阱狀態(tài)）0,1S0,10,10,10,10,10,10,10,10,110,1（9） x|x0 ，1 +且 x 以 0 開(kāi)頭以（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1 結(jié)尾1 時(shí)，進(jìn)入陷阱狀態(tài)）S0001110,1（10） x|x0 ， 1 +且 x 中至少含有兩個(gè) 100,111010（11） x|x0 ， 1 +且如果 x 以 1 結(jié)尾，則它的長(zhǎng)度為偶數(shù)；如果x 以 0 結(jié)尾，則它的長(zhǎng)度為奇數(shù) 可將 0 ，1 +的字符串分為4 個(gè)等價(jià)類。q

4、0： 的等價(jià)類，對(duì)應(yīng)的狀態(tài)為終止?fàn)顟B(tài)q1:x 的長(zhǎng)度為奇且以0 結(jié)尾的等價(jià)類q2： x 的長(zhǎng)度為奇且以1 結(jié)尾的等價(jià)類q3: x 的長(zhǎng)度為偶且以0 結(jié)尾的等價(jià)類q4: x 的長(zhǎng)度為偶且以1 結(jié)尾的等價(jià)類q1q4q0100S011q3011q 2（12） x|x 是十進(jìn)制非負(fù)數(shù)0S0， 1， 2， 3， 4，5，6，7，8，91， 2， 3， 4， 5，6，7，8，9.0， 1， 2， 3， 4，5，6，7，8，9（ 13）S（ 14）S* 2.(1)x x0,1且x中不含形如 00的子串1S100111(2) x x0,1 且x中含形如 10110的子串10110，100，1(3) x x0,

5、1且x中不含形如 10110的子串101100，10， 1(4) x x0,1 和x的倒數(shù)第 10個(gè)字符是 1，且以 01結(jié)尾 0，110，10，10， 10，1100，10，10， 1(5) x x0,1且x以0開(kāi)頭以1結(jié)尾0， 101(6) x x0,1且x中至少含有兩個(gè) 10，10，10，1S110，1(7) x x0,1 * 且如果 x以 1結(jié)尾，則它的長(zhǎng)度為偶數(shù)；如果以 0結(jié)尾，則它的長(zhǎng)度為奇數(shù)1S0，10(8) x x 0,1且x的首字符和尾字符相等 00， 100110， 11(9) x xT x,0,1 0,100110,1*3.根據(jù)下列給定文法，構(gòu)造相應(yīng)的FA 。（敖雪峰02282068）(1) 文法 G1的產(chǎn)生式集合如下：G1: S a|AaA a|Aa|cA|BbB a|b|c|aB|Bb|Cb(2) 文法 G2的產(chǎn)生式集合如下：G2: S a|AaA a|Aa|Ac|BbB a|b|c|B