question:1107810311

決定性有限オートマトンに関する問題です.
「長さ5の部分記号列を調べれば,少なくとも2つの0を含む全ての記号列からなる言語」を受理するDFAを与えよ.
というのがあるのですが,規模が大きくなりすぎてしまいます.何かスマートな方法があるはずなのですが,詳しい解説などを参照できるページを教えてください.

正規表現できれば勝ち。なんにせよ一度書けたのなら縮小する手段はある。適当にNDFAで書いてそれを決定性にすりゃいいし。
で、考えるにこれが一番スマートか。

うん、NDFAとか正規表現とか考えずに書けたな。一番右の部分で直近5個中0が何個あったかを記憶しておくという話。長さ5の部分記号列とあるので、これが最簡形か。規模が大きくってのが状態数にして何個なのかよぉ分からんので答えるには微妙。

DFAヴァージョン
間違えてた。0/5と1/5のところは同値だから潰せる。

更に間違えてたので修正。どこら辺から潰せるか考えるのが面倒だ。
DFAヴァージョン 修正版

from google

講義記録 神戸大林先生の講義の質問とそれに対する回答。なかなかとぼけた質問が多くて和む。