形式語言與自動機(jī)理論試題-預(yù)覽頁
【正文】 1,q2,q3][q0,q1, q2]參 考 題 目設(shè)，構(gòu)造下列語言的文法。所以，L不是RL。不妨設(shè)N是泵引理所指的僅依賴于 L的正整數(shù)，取Z= 顯然，Z∈L 。{0，1}+且x的第十個(gè)字符為1} （設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為0，進(jìn)入陷阱狀態(tài)） 二、判斷（正確的寫T，錯(cuò)誤的寫F） 5x2 {a,b,c,d,e}上的二元關(guān)系，則 ( T ) 任取(x.,y),其中x,y，使得。{0，1}+且x以0開頭以1結(jié)尾} （設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)） (2) {x|x206。假設(shè)L是RL，則它滿足泵引理。不妨設(shè)v=，k=1 此時(shí)有u= ，w= 從而有uvw= 當(dāng)i=2時(shí)，有uvw= 又因?yàn)閗=1,所以 N+kN 這就是說不屬于L， 這與泵引理矛盾。（10分）解：處理輸入串00001000的過程中經(jīng)歷的ID變化序列如下： 00001000 00001000 00001000 00001000 000010000000010000 00001000 00001000 00001000 00001000B 處理輸入串10000的過程中經(jīng)歷的ID變化序列如下： 10000 100000 10000 10000 10000 10000 10000B七、根據(jù)給定的NFA，構(gòu)造與之等價(jià)的DFA。 (2) 。 解答：。 解答： 。 解答： 。設(shè)文法G有如下產(chǎn)生式： S→aB│bAA→a│aS│bAAB→b│bS│aBB證明L(G)＝{ω│ω中含有相同個(gè)數(shù)的a和b，且ω非空}。當(dāng)|y| = n時(shí)，假設(shè)原式成立，故當(dāng)|y|= n+1時(shí)，不妨設(shè)y = wa, |w| = n, |a| = 1根據(jù)DFA定義，故原式成立，同理可證，對任意的y來說，結(jié)論也是成立的。Σ*x206。δ（q,x）206。Σ*并且x207。為了證明，我們在的基礎(chǔ)上，其中，即所有確定化后的狀態(tài)都為終結(jié)狀態(tài)。對q∈Q2{f2}，a∈∑∪{ε} δ(q，a)=δ2(q，a)； 3) δ(f1，ε)={q02} 要證 ，只需證明 ， 1. 證明 2) 再證明 *******************************************************************************（吳丹 02282090）23. FA M的移動函數(shù)定義如下: δ(q0,3)={q0}δ(q0,1)={q1}δ(q1,0)={q2}δ(q1,1)={q3}δ(q2,0)={q2}δ(q3,1)={q3}其中,q2,q3為終態(tài).(1) M是DFA嗎?為什么?不是,因?yàn)椴⒉皇撬械臓顟B(tài),在接收一個(gè)字母表中的字符時(shí)會有一個(gè)狀態(tài)與之對應(yīng).(2) 畫出相應(yīng)的DFA的狀態(tài)轉(zhuǎn)移圖(3) 給出你所畫出的DFA的每個(gè)狀態(tài)q的set(q):set(q)={x|x206。0,
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1