ミニテスト12解答 月曜３校時 大月 美佳.

Presentation on theme: "ミニテスト12解答 月曜３校時 大月 美佳."— Presentation transcript:

1 ミニテスト12解答 月曜３校時 大月 美佳

2 前回のミニテスト 演習問題 3.25 以下のDFAを最小化せよ。 e 1 開始 h f g a d b c 1 1

3 ステップ1 最終状態とそうでない状態の組にXをつける。 h g f e d c b a X

4 ステップ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

5 ステップ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

6 ステップ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)

7 ステップ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)

8 ステップ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

9 ステップ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

10 ステップ8 最終解 a≡g b≡f c≡e 開始 h [a,g] d [b,f] 1 [c,e]