2005年08月03日
DFAの最小化
- 2005-08-03 (Wed)
- アカデミック？
とあるDFAを使うプログラムに「最小のオートマトンを求める」というコメントの付いた関数があった．んで，全ての入力に対して同じ状態へ遷移する状態集合だけをまとめて最小だと叫んでいる．これだけじゃ明らかに最小にはならないのに… このプログラムの作者は何も考えてないんだなぁと思わざるを得ない．最小化できない例としてもっとも単純に考えられるのは，あらゆる入力に対して自分自身に帰ってくるような状態が二つ以上ある場合で，このとき遷移先の状態は各々異なっているので状態がまとめられない．ということで，正しく最小化するには逆の考えをとらねばならない．すなわち，明らかに異なることをチェックしていき，異なると示せないものを等価とする．
- Comments: 0
- TrackBack (Close): -