計算の理論 I －数学的概念と記法－

ミニテスト12解答
月曜３校時
大月美佳
前回のミニテスト
演習問題 3.25
以下のDFAを最小化せよ。
1
a
0
0
開始
b
1
1
1
c
0
0
d
0
e
11
1
f
0
0
1
g
0
h
ステップ1
 最終状態とそうでない状態の組にXをつ
ける。
h
g
f
e
d
a
X
b
X
c
X
d
e
f
g
X
X
X
X
c
b
ステップ2
1
aについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
0
1
h
(a, b)
(b, a)
(a, c)
a
(a, c)
(b, d)
(a, b)
b
X
(a, e)
(b, d)
(a, f)
c
X
d
(a, f)
(b, g)
(a, e)
(a, g)
(b, f)
(a, g)
f
(a, h)
(b, g)
(a, d)
g
e
g
f
X
X
X
X
e
d
c
b
X
X
X
X
X
h
ステップ3
1
bについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
0
1
h
(b, c)
(a, d)
(c, b)
a
(b, e)
(a, d)
(c, f)
b
(b, f)
(a, g)
(c, e)
(a, f)
(c, g)
(b, h)
(a, g)
(c, d)
f
e
d
c
b
X
X
X
X
X
X
X
X
X
c
d
(b, g)
g
e
f
g
X
X
X
X
X
h
ステップ4
1
cについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
0
1
(c, e)
(d, d)
(b, f)
a
X
(c, f)
(d, g)
(b, e)
b
X
X
(c, g)
(d, f)
(b, g)
c
X
X
X
d
X
X
X
(c, h)
(d, g)
(c, g)→(b, g)→(a, f)
(b, d)
h
e
f
g
g
f
e
d
c
b
X
X
X
X
X
X
X
X
X
X
h
ステップ5
1
eについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
0
1
(e, f)
(d, g)
(f, e)
a
X
(e, g)
(d, f)
(f, g)
b
X
X
(e, h)
(d, g)
(f, d)
c
X
X
X
d
X
X
X
e
X
X
X
(c, g)→(b, g)→(a, f)
h
f
g
g
f
e
d
c
b
X
X
X
X
X
X
X
X
X
X
h
ステップ6
1
fについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
0
1
h
(f, g)
(g, f)
(e, g)
a
X
(f, h)
(g, g)
(e, d)
b
X
X
c
X
X
X
d
X
X
X
e
X
X
X
f
X
X
g
g
f
e
d
c
b
X
X
X
X
X
X
X
X
X
X
h
ステップ7
1
gについて
a
0
1
b
0
c
0
0
d
0
1
e
1
f
1
0
1
g
0
0
開始
(g, h)
a≡g
b≡f
c≡e
0
1
(f, g)
(e, d)
h
g
f
e
d
c
b
X
X
X
X
X
X
X
X
a
X
b
X
X
c
X
X
X
d
X
X
X
e
X
X
X
f
X
X
g
X
X
X
h
ステップ8
最終解
a≡g
b≡f
c≡e
1
開始
[a,g]
0
1
[b,f]
0
1
0
h
[c,e]
0
1
1
0
d

Download Report