Home > アカデミック? > DFAの最小化

DFAの最小化

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

★下記に2つの英単語をスペースで区切って入力してください

Home > アカデミック? > DFAの最小化

Search
Feeds

Page Top