ディジタル回路 - alabama_country @Wiki

試験直前のあがき

状態機械の最小化とは？

状態機械の最小化に関する過去問があるので今年も同様の出題が予想されるが、何を教科書が言っているのかよく分かっていないため今からここに自分の為にドキュメントとする。

状態の等価性

有限状態機械の説明は簡単であるため省く。で、それぞれの状態が等しいということは、状態S_i, S_jに対しどのような入力を与えても同じ出力を吐くと言うことになるけど、これが完全に等価であるということを証明するのは不可能らしい（無限の可能性が感じられますか？）。というわけで、kの長さの入力に対して等しい出力を返すような状態S_i, S_jをk等価であるという。一方ある入力に対して異なる出力を吐く場合はk識別可能、その時の入力を識別系列という。

等価性による分割

という訳でブロック分けしていく。

1. まず、長さ1の入力に対しての出力が等しいかどうかで状態を分類する。これで1等価性による分割が出来たことになる。
2. 次に2の入力に対して等しいかどうかで分類します。だが、一から分類するのは愚の骨頂というもので、2つの入力に対して等しいなら当然1つの入力に対しても等しいので、先のグループ内での分類になる。ここで、2つ目の入力が等しいかどうかを見るには、1つ目の入力に対する次状態がさっきのグループのどれであるかで分類できる。これを使えばさらに分類できる。
3. 後はグループのラベルを更新して同じことを有限回繰り返せば分割が出来ないとこまで分割できる。この結果が分割数最少の状態機械である。で、これが最小化ってこと。

何のために最小化するのか？

結局は有限状態機械というのを論理回路で構築する際には状態値と入力から生成できればいい。ある入力に関して必ず同じ出力を返す場合には状態値ってのは同じでいい―――本当だろうか？とりあえず本当ということにして問題を解きたい。