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