オ ート マト ン ・ 形式言語 演習問題解答例 2015 1. 年 12 月 15 日 M1 の拡張遷移関数と 受理状態集合を それぞれ Æ1 と F1 と おく ． M2 について も 同様に Æ2 と F2 と おく ． (a) i. 空列 ． q1 は受理状態である が q4 は受理状態でな いため， q1 と q4 は区別可能である ． 定義に = q1 2 F1 であ る が， Æ1 (q4; ") = q4 < F1 であ る ． そ のた め， 定義よ り q1 と q4 は区別可能であ る ． 解説: 従え ば， 入力系列と し て " を 考え た 場合， Æ1 (q1 ; ") ii. 00 や 10． 解説: 入力系列が 00 の場合， Æ1 (q1 ; 00) = q5 q1 と q5 が区別可能であ る こ と が分かる ． より， 00 や 2 F1 であ る が， よ り 短い入力系列と し て ， 10 Æ1 (q1 ; 0) = q2 < F1 かつ， Æ1 (q5 ; 0) 0， 1 10 Æ1 (q5 ; 00) = q3 < F1 であ る こ と の場合も 同様． お よ び " があ る ． し かし ， 入力系列が = q4 < F1 であ り ， 0 の場合， いずれも 受理状態に 遷移し な いた め， 区別可能であ る こ と は示せな い． 入力系列が 1 の場合も 同様であ る ． " の場合は共に 受理状 態に と ど ま る ので区別可能であ る こ と は示せな い． (b) 最低でも n 2 の長さ の入力系列が必要であ る ． 最短と な る のは n 2 個の 0 だけ が並んだ系列 であ る ． 解説: M2 に おいて ， q2 から 受理状態 qn ま で推移する 最短の入力系列は， n 2 個の 0 だけ が並 2 n 2 ) = qn 2 F 2 である が， Æ2 (q1 ; 0 ) = qn 1 < F 2 である ． よ っ て ， q1 と んだ系列である ． Æ2 (q1 ; 0n q2 は区別可能であ る こ と が分かる ． n 2 よ り 短い入力系列 w が与え ら れて も ， Æ2 (q1; w) も Æ2(q2 ; w) も 受理状態ではな いので， 区別 可能である こ と は示せない． し たがっ て ， q1 と q2 を 区別する 最短入力系列の長さ は n 2 である ． 2. M3 に 穴埋めア ルゴ リ ズム を 適用する と ， 状態の区別可能性に ついて の表 (左下表) が得ら q1 q2 ， q3 q4 で あ る こ と が分かる ． こ のこ と から ， q1 と q2 を p1 ， q3 と q4 を p2 に ， そ れぞれ 1 つの状態に ま と めて ， M3 と 等価な 最小の DFA（ 右下図） が得ら れる ． (a) DFA れる ． 表よ り ， q1 q2 q3 q4 0 q0 q1 q2 q3 q0 1 p1 0 1 p2 1 等価な 最小 DFA の状態遷移図 状態の区別可能性の表 M4 に 穴埋めア ルゴ リ ズム を 適用する と ， 状態の区別可能性に ついて の表 (左下表) が得ら p0 p3 ， p1 p4 であ る こ と が分かる ． こ のこ と から ， p0 と p3 を q0 ， p1 と p4 q1 に ， そ れぞれ 1 つの状態に ま と めて ， M4 と 等価な 最小の DFA が得ら れる ． (b) DFA れる ． 表よ り ， を 0 1 a p1 p2 p3 p4 pe a q0 p0 p1 p2 p3 p4 b q1 b p2 b a pe a,b 状態の区別可能性の表 等価な 最小 DFA の状態遷移図 M5 () DFA に 穴埋め ア ルゴ リ ズム を 適用する と ， 状態の区別可能性に つ いて の表 (左下表) が得 ら れる ． 表よ り ， を そ れぞれ順に ， q1 q2 q3 q4 q5 q6 q7 q0 q4， q1 q5 ， q2 q6 ， q3 q7 で あ る こ と が分かる ． 同値な 状態組 p0 ; p1 ; p2; p3 と ま と める と ， M5 と 等価な 最小の DFA（ 右下図） が得ら れる ． q0 q1 q2 1 p0 q3 q4 q5 q6 1 1 p1 0 1 0 p3 0 p2 等価な 最小 DFA の状態遷移図 状態の区別可能性の表 M7 を 一緒に し て 穴埋めア ルゴ リ ズム を 適用する と 以下のよ う に な る ． 右の表よ り ， p0 p4 q0 q3 ; p1 p2 q1 ; p3 q2 p1 である こ と が分かる ． M6 の初期状態 p0 と M7 の初期 p2 状態 q0 に ついて p0 q0 であ る から ， M6 と M7 は等 p3 価であ る ． p4 q0 q1 q2 q3 p0 p1 p2 p3 p4 q0 q1 q2 3. DFA M6 と 0 DFA a (別解) DFA M6 と DFA M7 に， それぞれ穴埋めアルゴ リ ズム を 適用し て 最小化する と ， 右図のよ う に な る ． こ のよ う に同じ オート マ ト ン に最小化でき る から ， と M7 は等価であ る ． M6 b b a a,b 2
© Copyright 2024 ExpyDoc
