0

形式言語（Aho's、Hopcroft）は独学で学んでいますが、正規表現が苦手です。

私は単純なタスクに取り組むことができましたが、これは少なくとも私にとっては挑戦でした. ここまで数えられない場合の解決方法、私はこの種の計算に慣れていません。
正規表現として表現できるほど答えを一般化できるプロパティまたは何かがあるに違いありません。

これまでのところ、少なくとも 2 ～ 3 のケースが存在する可能性があると考えています。

  • sum=3k の場合、mod3=0 を合計します。
  • sum=3k+1 の場合、mod3=1 を合計します。
  • sum=3k+2 の場合、mod3=2 を合計します。

しかし、合計が発生するには多くの組み合わせがある可能性があるため、正規表現が従わなければならないパターンを見つけることができないことに気づきました。

exの文字列。{122211}0（中括弧は読みやすくするためのものです）{sum=3k}0exの文字列から合計が「10」の場合、それが保持されるため、最後にゼロがあります。{1222111}1場合によって{sum=3k+1}は、最後にある必要があるなどです。

これは問題に取り組むための正しい道であるかもしれませんし、そうでないかもしれませんが、どんな提案も歓迎します。どんな助けも大歓迎です。

4

1 に答える 1

0

ヒントは次のとおりです。どのような明確な最終状態になる可能性があるかを考えてください。値の数は3つの異なるものになる可能性があるため、少なくとも3つの状態があります。また、空の文字列は受け入れられないため、明確な開始状態が必要です。もっと州が必要ですか？

ヒント2：開始状態と他の9つの状態を使用してDFAを使用すると、これを簡単に実行できると思います。そのうち3つだけが受け入れられます。

編集：DFAを取得したら、Kleeneの定理を使用して同等の正規表現を作成できます。正規表現をまっすぐに実行したい場合は、別のヒントがあります。長さ3kの文字列を表示している場合は、次のように追加できます。長さが1で、その後に1が続く任意の文字列。長さ2、続いて2の任意の文字列。したがって、長さ3k、1、および2の文字列の正規表現を記述できれば、実質的には完了です。

于 2012-02-04T13:15:10.790 に答える