人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

決定性有限オートマトンに関する問題です.
「長さ5の部分記号列を調べれば,少なくとも2つの0を含む全ての記号列からなる言語」を受理するDFAを与えよ.

というのがあるのですが,規模が大きくなりすぎてしまいます.何かスマートな方法があるはずなのですが,詳しい解説などを参照できるページを教えてください.

●質問者: nakaie
●カテゴリ:学習・教育 科学・統計資料
✍キーワード:DFA オートマトン スマート 言語
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● dasm
●10ポイント

http://f.hatena.ne.jp/dasm/20050208101140

dasm's fotolife

末尾の 0 が何番目にあるかで場合分けすると多少は少なくなります。


2 ● shampoohat
●10ポイント

http://www.google.co.jp/search?hl=ja&q=%E6%9C%80%E9%81%A9%E5...

「規模が大きくなりすぎ」って可愛らしいですね。「0」が1個出てきてから次の4回以内に再び「0」がもう一個出てくれば受理なんですから、そう読みかえてから作れば次の5状態で出来ます。この読み換えを機械がやってくれるようになるのは、まだ先ですかね。

状態0s:(0→状態1、非0→状態0)

状態1:(0→受理、非0→状態2)

状態2:(0→受理、非0→状態3)

状態3:(0→受理、非0→状態4)

状態4:(0→受理、非0→状態0)


3 ● matsu911
●130ポイント

http://hp.vector.co.jp/authors/VA007799/viviProg/doc_regexp.htm

正規表現

0以外の文字が3つ続くことはない、と思うのですが、いかがでしょう?

http://aglaia.c.u-tokyo.ac.jp/~yamamoto/Yamaguch_Seminar/2001100...

http://www.oreilly.co.jp/books/4873111307/toc.html

O'Reilly Japan - 詳説 正規表現 第2版

◎質問者からの返答

遅くなりました.詳しいサイトの紹介をありがとうございます.

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ