2015/7/3
演習問題
第2回の演習の解答
1．a(b+c)*aに対応する有限オートマトンの状態
遷移図を書いてみましょう.
2．図の有限オートマトンの受理する言語を説
明してください．
知能システム科学
新田克己
解答
１．
演習問題
１．以下の「宣教師と人喰い人の問題｣の状態遷移図
を書きなさい．
b,c
q0
a
２．
0* ＋ 0*11*
q1
a
q2
+
0* ＋ 0*1
３人の宣教師と３人の人喰い人が川の左岸にいる．
1艘の小船を使って全員が右岸に渡りたいが，小船
には最大2人しか乗れず，左岸，右岸いずれでも人
喰い人の数が宣教師の数より多いと宣教師は人喰
い人に食べられてしまう．全員が安全に右岸に渡る
にはどうすればよいだろう．
宣教師と人喰い人の問題
解答
331 000
MC→
←MC
MM→
010 321
130 201 CC→
220 111
M←
111 320
MC→
031 300
000 331
C←
M←
321 010
020 311
MM→
CC→
300 031
221 110
C←
MC←
311 020
MM→
（注意）
主要部のみ記載
110 221
1
2015/7/3
演習問題
解答
0 1
2．非決定性有限オートマトンを決定性オートマ
トンに変換しなさい．
{q0} {q0,q1} {q0} 0
1
M=<{q0, q1, q2},{0,1},q0,{q2} ,δ >
δ(q0,0)={q0,q1}, δ(q0,1)={q0}
δ(q1,1)={q2}
０, 1
0
{q0,q1}
0
q1
q2
{q0,q2} {q0,q1} {q0}
{q0}
０
q0
{q0,q1} {q0,q1} {q0,q2}
１
1
1
{q0,q2}
2
© Copyright 2024 ExpyDoc
