決定性有限オートマトンに関する問題です.

「長さ5の部分記号列を調べれば,少なくとも2つの0を含む全ての記号列からなる言語」を受理するDFAを与えよ.

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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/02/08 06:05:11
  • 終了:--

回答(3件)

id:dasm No.1

dasm回答回数66ベストアンサー獲得回数02005/02/08 10:17:26

ポイント10pt

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

id:shampoohat No.2

shampoohat回答回数347ベストアンサー獲得回数02005/02/09 00:54:40

ポイント10pt

「規模が大きくなりすぎ」って可愛らしいですね。「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)

id:matsu911 No.3

matsu911回答回数136ベストアンサー獲得回数02005/02/08 09:02:56

ポイント130pt

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

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

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

id:nakaie

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

2005/02/09 16:45:11
  • id:smoking186
    全員間違ってます。

    2,3と回答オープンしたのでツッコミ。

    1の場合, 11011が受理されるのでアウト。
    2の場合も11011が受理されるのでアウト。
    3の場合, 1111100が受理されるのでアウト。

    質問者が正しい答えを得ることを祈ります。
  • id:smoking186
    訂正:

    失敗。
    1,2は確実に間違ってますね。
    で、
    -任意の長さ5の文字列を取る
    -2つ以上0を含む長さ5の文字列を取れる
    のどちらで解釈するかによって変わってきます。
    後者の場合は3であってますね。
    前者の場合は3でも駄目です。状態数が膨大になるのでこっちが質問者の意図したものですかね。さてはて。
  • id:dasm
    Re:全員間違ってます。

    突っ込みありがとうございます。
    全くその通りでございます。申し訳ないです。
    状態数の確認しかしなかったのでこういう事になってしまいました。
  • id:shampoohat
    Re:訂正:

    >で、
    >-任意の長さ5の文字列を取る
    >-2つ以上0を含む長さ5の文字列を取れる
    >のどちらで解釈するかによって変わってきます。

    おぉ、ナイス突っ込みです。

    >後者の場合は3であってますね。
    >前者の場合は3でも駄目です。状態数が膨大になるのでこっちが質問者の意図したものですかね。さてはて。

    前者の場合だったとしても1,2をちょっと換えればOkじゃないかと。
    ・0を2こ受理したら、状態から状態’に遷移する(2こだから状態→状態’’→状態’)
    ・状態(状態’’)で終端が入力されたら受理しない
    ・状態’で終端が入力されたら受理する
    で。
    だいたい12状態あれば良さそうですけど、膨大です?
  • id:dea1man
    このでたらめな回答は何ですか?

    説明になっていません。専門でもないロクに知りもしない事を、さも知っているようなフリをして想像で答えないで頂きたい。
    全くもって見当外れのでたらめです。
    推敲してから書きなさい。
  • id:dasm
    Re(2):訂正:

    >>で、
    >>-任意の長さ5の文字列を取る
    >>-2つ以上0を含む長さ5の文字列を取れる
    >>のどちらで解釈するかによって変わってきます。
    >
    >おぉ、ナイス突っ込みです。
    >
    >>後者の場合は3であってますね。
    >>前者の場合は3でも駄目です。状態数が膨大になるのでこっちが質問者の意図したものですかね。さてはて。
    >
    >前者の場合だったとしても1,2をちょっと換えればOkじゃないかと。
    >・0を2こ受理したら、状態から状態’に遷移する(2こだから状態→状態’’→状態’)
    >・状態(状態’’)で終端が入力されたら受理しない
    >・状態’で終端が入力されたら受理する
    >で。
    >だいたい12状態あれば良さそうですけど、膨大です?

    長さ 1 から 4 のものも受理できないようにできますか?
  • id:dasm
    補足

    終端記号が入力に入らないと仮定した場合です。
    入っていると考えるのが普通のような気がしますが、「状態数が膨大」になるという話を質問者の方がされていたので、そこがちょっと引っかかりました。
  • id:dasm
    お礼に

    突っ込み返しをしようと企んでいましたが、既にご自分で修正されてますね。
    35 より減らせる方法を誰かご存知でないでしょうか。
    http://f.hatena.ne.jp/dasm/20050209233749
  • id:DirectY
    Re(2):全員間違ってます。

    >突っ込みありがとうございます。
    >全くその通りでございます。申し訳ないです。
    >状態数の確認しかしなかったのでこういう事になってしまいました。
    >
    aki73ixと同じじゃねぇか
  • id:dealmanco
    Re(3):全員間違ってます。

    >>突っ込みありがとうございます。
    >>全くその通りでございます。申し訳ないです。
    >>状態数の確認しかしなかったのでこういう事になってしまいました。
    >>
    >aki73ixと同じじゃねぇか

    http://www.hatena.ne.jp/1083055468

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません