question:1107810311
決定性有限オートマトンに関する問題です．
「長さ5の部分記号列を調べれば，少なくとも2つの0を含む全ての記号列からなる言語」を受理するDFAを与えよ．
というのがあるのですが，規模が大きくなりすぎてしまいます．何かスマートな方法があるはずなのですが，詳しい解説などを参照できるページを教えてください．
正規表現できれば勝ち。なんにせよ一度書けたのなら縮小する手段はある。適当にNDFAで書いてそれを決定性にすりゃいいし。
で、考えるにこれが一番スマートか。
うん、NDFAとか正規表現とか考えずに書けたな。一番右の部分で直近5個中0が何個あったかを記憶しておくという話。長さ5の部分記号列
とあるので、これが最簡形か。規模が大きく
ってのが状態数にして何個なのかよぉ分からんので答えるには微妙。
間違えてた。0/5と1/5のところは同値だから潰せる。
更に間違えてたので修正。どこら辺から潰せるか考えるのが面倒だ。
