計算理論課后習題答案.pptVIP

第一章習題 1 給定文法G S B C D E 0 1 P S 其中P S ABC AB 0AD AB 1AE AB D0 0D D1 1D E0 0E E1 1E C DC B0C EC B1C 0B B0 1B B1試寫出句子01100110的派生過程 解 S ABC 0ADC 0AB0C 01AE0C 01A0EC 01A0B1C 01AB01C 011AE01C 011A0E1C 011A01EC 011A01B1C 011A0B11C 011AB011C 0110AD011C 0110A0D11C 0110A01D1C 0110A011DC 0110A011B0C 0110A01B10C 0110A0B110C 0110AB0110C 01100110C 01100110 2 設(shè)計下列各文法G 使得它們分別是 1 G是個上下文無關(guān)文法 且L G aibjck i j k 1 2 G是個正規(guī)文法 且L G aibjck i j k 1 3 G是個上下文無關(guān)文法 且L G wwR w 0 1 其中wR是w的逆轉(zhuǎn) 例如w 001 則wR 100 解 設(shè)計一個文法G要驗證 凡是符合要求的句子G都能產(chǎn)生出來 G產(chǎn)生出來的所有句子都是符合要求的 1 G S A B C a b c P S P S ABC A aA a B bB b C cC c 2 G S A B C a b c P S P S aA A aA bB B bB cC C cC 3 G S 0 1 P S P S 0S0 1S1 00 11 第二章習題 1 設(shè)計一個有限自動機 FA M 使得T M 中的每個句子w同時滿足下面三個條件 1 w a b 2 w 是3的整數(shù)倍 3 w以a開頭 以b結(jié)尾 解 2 設(shè)計二個FAM1和M2 分別滿足T M1 02i i是自然數(shù) T M2 02i 1 i 0 1 2 3 4 解 M1 3 給定NFAM1 p q r s 0 1 p s 如下表所示 構(gòu)造一個DFAM2 使得T M1 T M2 解 令M2 K q0 F 其中K 2K K 中的元素是由K的子集 q1 q2 qi 構(gòu)成 但是要把子集 q1 q2 qi 作為的一個狀態(tài)看待 因此把此子集寫成 q1 q2 qi q0 q0 F q1 q2 qi q1 q2 qi K 且 q1 q2 qi F K K 對 q1 q2 qi K a 有 q1 q2 qi a p1 p2 pj 當且僅當 q1 q2 qi a p1 p2 pj q0 p K 和F 以后確定 p 0 1 p q p p q p q r p r p r p q s p p q r p q r s p r p q s p q r s p r s p r s p q s p s p s p q s p s p q r s p q r s p r s K p p q p r p s p q r p q s p r s p q r s F p s p q s p r s p q r s 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 4 將下面的 NFAM等價變換成NFAM 對任何q K 任何a q a q a 解 M K q0 F q0是M的開始狀態(tài) 其中 公式 1 對于 q K q CLOSURE q 公式 2 對于 q K w a q wa CLOSURE q w a 因為f CLOSURE a a b 所以F F f q K 任何a q a q a 在計算 q a 時 要將a理解成a路徑 例如 a 0 a 0 c e d b 0 1 abcdef c e d b d b d b f f d b f d b f f d b 5 化簡正規(guī)表達式a aa a b b ab b 解 上式 a aa a b b其中 aa a 代表集合 aa aaaa aaaaaa a aa aaaa aaaaaa a aaa aaaaa a aa aaa aaaa aaaaa aaaaaa a 于是上式 aa b b a b b a b a b 6 構(gòu)造一個FAM 使得T M 的正規(guī)表達式為01 0 1 1 解 1 分解表達式 找出基本單元 0 1 01 1 設(shè)計接收這些基本單元的自動機如下 2 組裝 按照優(yōu)先權(quán)從高到低 01 0 1 1 1 0 1 0 1 7 給定FAM如下圖所示 求它所接收的語言T M 的正規(guī)表達式 解 8 將下面有限自動機簡化 要求有簡化過程 解 一 定義K上等價關(guān)系 給定DFAM K q0 F p q K p q 對 x 有 p x F q x F如果p q也稱p與q是不可區(qū)分的 二 商集K 三 的逆關(guān)系 p q x x p x F q x F x x p x F q x F p x F q x F x x 使得 p x 與 q x 恰有一個在F中 如果p q 稱p與q是可區(qū)分的 判斷p q是比較容易的 4 判斷可區(qū)分狀態(tài)對的算法引理2 1設(shè)M K q0 F 是DFA 則狀態(tài)對 p q 是可區(qū)分的 即p q 當且僅當在下面算法中 p q 格寫上 begin1 forp F q K F do給 p q 格寫 2 forF F或 K F K F 中每個狀態(tài)對 p q p q do3 if a 使得格 p a q a 內(nèi)已經(jīng)寫上 thenbegin4 給 p q 格寫 5 如果剛剛寫上 的格內(nèi)有先前寫入的狀態(tài)對 此狀態(tài)對的格同時也寫入 反復(fù)執(zhí)行5 直到寫入 的格內(nèi)沒有先前寫入的狀態(tài)對為止 endelse 格 p a q a 內(nèi)無 6 for每個a do7 把 p q 寫入格 p a q a 內(nèi) 除非 p a q a end 執(zhí)行此算法的結(jié)果用一個表表示 實際上 執(zhí)行此算法的過程就是向這個表內(nèi)寫入 的過程 b d a b be a c ba a d bf b c b d c d e f ea ef fe af dd fe 得 b d e f a a c c 于是K a b d c e f 五 構(gòu)造簡化的有限自動機定理2 5 1給定DFAM K q0 F 可根據(jù)引理2 1中的算法構(gòu)造出除去不可達狀態(tài)的具有更少狀態(tài)的DFAM 使得T M T M 證明 先對M用引理2 1中的算法求出K 再構(gòu)造M M K q0 F 其中K q q K 且在M中q是從q0可達的狀態(tài) F q q F 對任何 q K 任何a q a q a K a b d c e f a b c e b b d e e f K a b c e F e M K a F a b c e 0 1 a e q a q a 01 a b c e b c b e a a e e 9 給定DFAM如圖所示 求一個左線性文法G 使得L G T M 解 有兩種方法 方法11 先將M逆轉(zhuǎn)成M 2 根據(jù)M 構(gòu)造右線性文法G S A C A 0BB 0A 0C 1C 0C 1A 1B 1 3 將G 逆轉(zhuǎn)成左線性文法G S A C A B0B A0 C0 C1 0C A1 B1 1 P q ap q a p q a q a F 方法21 先根據(jù)M構(gòu)造右線性文法G A 0B 1C 1 其中A是開始變元 B 0A 1C 0 1C 0B 1B2 再將G 直接變成左線性文法G 根據(jù)定理 1 S 當且僅當S P 2 Ai 當且僅當S Ai P 3 Ai Aj 當且僅當Aj Ai P 4 S Aj 當且僅當Aj P 1 由A 1得 A 1 2 由A 0B得 B 0由A 1C得 C 1 3 由B 0A得 A B0由B 1C得 C B1由C 0B得 B C0由C 1B得 B C1 4 由B 0得 A B0由B 1得 A B1 方法21 先根據(jù)M構(gòu)造右線性文法G A 0B 1C 1 其中A是開始變元 B 0A 1C 0 1C 0B 1B因開始變元A出現(xiàn)在產(chǎn)生式右側(cè) 故引入新的開始變元S S A 其中S是開始變元 A 0B 1C 1 B 0A 1C 0 1C 0B 1B 2 再將G 直接變成左線性文法G 根據(jù)定理 1 S 當且僅當S P 2 Ai 當且僅當S Ai P 3 Ai Aj 當且僅當Aj Ai P 4 S Aj 當且僅當Aj P 2 S A得 A 3 由A 0B得 B A0由A 1C得 C A1由B 0A得 A B0由B 1C得 C B1由C 0B得 B C0由C 1B得 B C1 4 由A 1得 S A1由A 得 S A由B 0得 S B0由B 1得 S B1 整理得左線性文法G S A1 B0 B1 AA B0 B A0 C0 C1C A1 B1表面上看與方法1得結(jié)果略有些不同S A C A B0B A0 C0 C1 0C A1 B1 1 10 首先構(gòu)造一個右線性文法G 使得L G aibj i j 0 ck k 0 再構(gòu)造一個有限自動機M 使得T M L G 解 令G S A B C a b c P S P S A C A aA B B bB b C cC c 令M S A B C a b c S E c A a b 11 給定右線性文法G S B C D 0 1 P S 其中P S B C B 0B 1B 011 試求一個FAM 使得T M L G C 0D 1C D 0C 1D解 此題與第10題類似 要將G變成簡單右線性文法 唯一要處理的產(chǎn)生式是B 011 將它變成 B 0F F 1G G 1 12 證明L ai i是個素數(shù) 不是正規(guī)集 證明 1 假設(shè)L是正規(guī)集 2 令n是L滿足正規(guī)集泵作用引理常數(shù) 3 取z am m n且m是個素數(shù) z m n 根據(jù)正規(guī)集的泵作用引理 可將z寫成z uvw形式 其中 uv n v 1 且對任何i 0有uviw L 4 令u an1 v an2 w an3 于是 uv n1 n2 n v n2 1 n1 n2 n3 m z uvw an1 n2 n3 am uviw an1 in2 n3 a n1 n2 n3 i 1 n2 am i 1 n2取i m 1 則uvm 1w am m 1 1 n2 am mn2 am 1 n2 由于n2 1 所以1 n2 2 而m 2 所以m 1 n2 不是素數(shù) 故uvm 1w L 產(chǎn)生矛盾 所以L不是正規(guī)集 第三章習題 1 給定CFGG S A B C a b c P S 其中 P S A B A Ab bS C b B AB Ba C AS b 去掉G中的無用符號和單一生成式 解 定義 給定CFGG S 如果在G中存在派生S X w 其中w X 則稱符號X是有用的 否則X是無用的 利用兩個引理 去掉無用符號 注意 一定是先應(yīng)用引理3 2 1 后應(yīng)用引理3 3 2 引理3 2 1給定CFGG S 且L G 可以找到一個與G等價的CFGG S 使得每個A 都有w 且在G 中有A w 證明 1 求 的算法 begin OLD NEW A A w P且w WhileOLD NEW dobegin OLD NEW NEW OLD A A P 且 OLD end NEW end 引理3 2 2給定CFGG S 可以找到一個與G等價的CFGG G S 使得每個X 都有 且在G 中有派生S X 證明 1 執(zhí)行下面迭代算法求 和 1 置初值 S 2 如果A 在P中又有產(chǎn)生式A 1 2 m 則可以將 1 2 m中的所有變元加到 中 將 1 2 m中的所有終極符加到中 中 重復(fù)2 3 若沒有新的符號可加入到 中 算法停止 最后得到 P S A B A Ab bS C b B AB Ba C AS b 對G應(yīng)用引理3 2 1 執(zhí)行上述算法 得到的結(jié)果如下表所示 循環(huán)次數(shù)i初值123 OLD NEW A C S A C A C A C S A C S 最后得G CFGG S A C a b c P S 其中P S A A Ab bS C b C AS b實際上 只去掉了不能推出終極符串的變元B 再對G 應(yīng)用引理3 2 2 P S A A Ab bS C b C AS b再對G 用引理3 2 2處理 執(zhí)行算法的結(jié)果如下表所示 最后得G S A C b P S P S A A Ab bS C b C AS b實際上只去掉了無用符號a和c 下面對G 去掉單一產(chǎn)生式 對任何A B 如果有A B 且B 1 2 n是P 中B的所有非單一產(chǎn)生式 則把所有A 1 2 n加到P 中 P S A A Ab bS C b C AS b下面去掉單一產(chǎn)生式S A A C 得P S Ab bS C b A Ab bS AS b C AS b再去掉S C 得S Ab bS AS b A Ab bS AS b C AS b但是 可以看出C是無用符號 所以C AS b也被去掉 最后得 G S A b P S P S Ab bS AS b A Ab bS AS b 2 給定CFGG S A B C a b P S 其中 P S ABC A BB B CC a C AA b 去掉G中的 生成式 解 首先求出可為零的變元 即可以推出 的變元 顯然有A C B和S 如果A X1X2 Xn P 則將所有形如A 1 2 n的產(chǎn)生式都加到P 中 其中 如果Xi不是可為零的 則 i Xi 如果Xi是可為零的 則 i Xi或者 i 但是 如果所有Xi i 1 2 n 都是可為零的 則不可所有 i 于是最后得 S ABC BC AC AB C B A A BB B B CC C a C AA A b 3 給定CFGG S A 0 1 P S 其中 P S AA 0 A SS 1 將G寫成GNF形式 解 此時G已經(jīng)具備CNF形式 A BC D a 1 變元重新命名 令A(yù)1 S A2 A P A1 A2A2 0 A2 A1A1 1 2 處理A2 A1A1 1 變成 A2 A2A2A1 0A1 1 3 處理左遞歸A2 A2A2A1 0A1 1 變成 A2 0A1 1 0A1Z2 1Z2 Z2 A2A1 A2A1Z2 4 處理A1 A2A2 0 得A1 0A1A2 1A2 0A1Z2A2 1Z2A2 0 5 處理Z2 A2A1 A2A1Z2 分別得 Z2 0A1A1 1A1 0A1Z2A1 1Z2A1Z2 0A1A1Z2 1A1Z2 0A1Z2A1Z2 1Z2A1Z2 最后得G A1 A2 Z2 0 1 P A1 P A1 0A1A2 1A2 0A1Z2A2 1Z2A2 0A2 0A1 1 0A1Z2 1Z2 Z2 0A1A1 1A1 0A1Z2A1 1Z2A1Z2 0A1A1Z2 1A1Z2 0A1Z2A1Z2 1Z2A1Z2 4 構(gòu)造一個PDAM 使得T M w w a b w中a b的個數(shù)相等 解 設(shè)計思想 有兩個狀態(tài)q1和q2 q1是開始狀態(tài) q2是終止狀態(tài) 棧內(nèi)符號 A B R R是開始時棧內(nèi)符號 開始時 讀a 向棧壓入A 讀b 向棧壓入B 之后 當讀a時 如果棧頂是A 再向棧壓入一個A 如果棧頂是B 則B退棧 當讀b時 如果棧頂是B 再向棧壓入一個B 如果棧頂是A 則A退棧 如果w中a b的個數(shù)相等 則M讀完w后 棧頂應(yīng)該是R 此時M進入終止狀態(tài)q2 令M q1 q2 a b A B R q1 R q2 q1 a R q1 AR q1 b R q1 BR q1 a A q1 AA q1 a B q1 q1 b A q1 q1 b B q1 BB q1 R q2 如w bbabaa時 M識別w的過程 表示ID間的變化 q1 bbabaa R q1 babaa BR q1 abaa BBR q1 baa BR q1 aa BBR q1 a BR q1 R q2 再如w abbab 看看M是如何拒絕接收的 q1 abbab R q1 bbab AR q1 baa R q1 aa BR q1 a R q1 AR 無下一個動作 w T M 5 給定CFGG S A B a b c P S 其中P為 S aAB aAA bSa Ab Bc b 求一個PDAM 使得T M L G 解 1 先簡化G 因為G中無 產(chǎn)生式和單一產(chǎn)生式 所以只去掉無用符號 對G應(yīng)用引理3 2 1 執(zhí)行上述算法 得到的結(jié)果如下表所示 得G S A a b c P S P S aAA bSa Ab b 循環(huán)次數(shù)i初值123 OLD NEW A S A A A S A S P S aAA bSa Ab b 再對G 應(yīng)用引理3 2 2處理 執(zhí)行算法的結(jié)果如下表所示 得G S A a b P S P S aAA bSa Ab b 2 將G 變成GNF形式先變成 S aA A bSD Ab b D a 處理左遞歸A Ab bSD b 變成 A bSD b bSDZ bZ Z b bZ最后得 S aA A bSD b bSDZ bZ Z b bZ D a S aA A bSD b bSDZ bZ Z b bz D a 3 根據(jù)上述文法 構(gòu)造PDAM 使得N M L G M q a b S A D Z q S 由S aA得 q a S q A 由A bSD b bSDZ bZ得 q b A q SD q q SDZ q Z 由Z b bz得 q b Z q q Z 由D a得 q a D q 4 根據(jù)M 變成M 使得T M N M M q0 q q1 a b S A D Z E q0 E q1 q0 E q SE q a S q A q b A q SD q q SDZ q Z q b Z q q Z q a D q q E q1 6 給定PDAM q0 q1 0 1 Z0 X q0 其中 如下 q0 1 Z0 q0 XZ0 q0 1 X q0 XX q0 0 X q1 X q0 Z0 q0 q1 1 X q1 q1 0 Z0 q0 Z0 求一個CFGG使得L G N M 解 令M K q0 Z0 N M L 構(gòu)造一個CFGG S 其中 q A p q p K A S 0 1 S q0 Z0 q0 q0 Z0 q1 q1 Z0 q0 q1 Z0 q1 q0 X q0 q0 X q1 q1 X q0 q1 X q1 P中產(chǎn)生式有三種類型 1 對任何q K 有S q0 Z0 q 1 S q0 Z0 q0 2 S q0 Z0 q1 2 對K中任何q q1 q2 qm qm 1 p 任何a 任何A B1 B2 Bm 只要 q a A 中含有 q1 B1B2 Bm 則有產(chǎn)生式 q A p a q1 B1 q2 q2 B2 q3 qm Bm p 由 q0 1 Z0 q0 XZ0 3 q0 Z0 q0 1 q0 X q0 q0 Z0 q0 4 q0 Z0 q0 1 q0 X q1 q1 Z0 q0 5 q0 Z0 q1 1 q0 X q0 q0 Z0 q1 6 q0 Z0 q1 1 q0 X q1 q1 Z0 q1 由 q0 1 X q0 XX 得7 q0 X q0 1 q0 X q0 q0 X q0 8 q0 X q0 1 q0 X q1 q1 X q0 9 q0 X q1 1 q0 X q0 q0 X q1 10 q0 X q1 1 q0 X q1 q1 X q1 由 q0 0 X q1 X 得11 q0 X q0 0 q1 X q0 12 q0 X q1 0 q1 X q1 由 q1 0 Z0 q0 Z0 得13 q1 Z0 q0 0 q0 Z0 q0 14 q1 Z0 q1 0 q0 Z0 q1 3 對任何q p K 任何a 任何A 如果有 q a A 中含有 p 則有產(chǎn)生式 q A p a 由 q0 Z0 q0 得15 q0 Z0 q0 由 q1 1 X q1 得16 q1 X q1 1下面對這些產(chǎn)生式進行整理 1 S q0 Z0 q0 2 S q0 Z0 q1 3 q0 Z0 q0 1 q0 X q0 q0 Z0 q0 4 q0 Z0 q0 1 q0 X q1 q1 Z0 q0 5 q0 Z0 q1 1 q0 X