9

私は正規表現を独学しており、3 で割り切れるすべての 2 進数 (およびそのような数のみ) を認識する正規表現を作成するという興味深い練習問題をオンラインで見つけました。正直に言うと、問題はそのようなシナリオの DFA を構築することを求めていましたが、正規表現を使用しても同様に可能であると考えました。

2 進数が 3 で割り切れるかどうかを判断するためのちょっとした規則があることは知っています。数字の偶数の場所にある 1 の数を取り、数字の奇数の場所にある 1 の数を引きます - これがゼロに等しい場合、数は 3 で割り切れます (例: 110 - 1 は偶数 2 スロットで、1 は奇数 1 スロットです)。ただし、これを正規表現に適応させるのに問題があります。

私が最も近づいたのは、数字が0になる可能性があることを認識しているため、それが最初の状態になります。また、3 で割り切れるすべての 2 進数は 1 で始まることも確認したので、それが 2 番目の状態になりますが、そこから立ち往生しています。誰か助けてくれませんか？

4

4 に答える 4

11

Oli Charlesworth の言うことに従って、基数bを特定の除数dで割り切れるように DFA を構築できます。DFA の状態は除算の残りを表します。

あなたの場合（基数2 - 2進数、除数d= 3 10）：

初期DFA

上記の DFA は、空の文字列を 3 で割り切れる「数値」として受け入れることに注意してください。これは、前にもう 1 つの中間状態を追加することで簡単に修正できます。

固定DFA

理論上の正規表現への変換は、通常のプロセスで実行できます。

再帰正規表現をサポートするフレーバーでの実用的な正規表現への変換は、DFA があれば簡単に行うことができます。これは、CodeGolf.SE からのこの質問の (base b= 10, d= 7 10 )の場合に示されています。

Ruby regex フレーバーで書かれた Lowjacker による回答の正規表現を引用させてください。

(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

分解すると、それがどのように構築されているかがわかります。アトミックグループ (または非バックトラッキンググループ、または所有的に動作するグループ) は、空の文字列の代替のみが一致することを確認するために使用されます。(?DEFINE)これは、 Perlでエミュレートするためのトリックです。そして、その数を7で割ったときの余り0～6に対応するAグループ。G

(?!$)
(?>
  (|(?<B>4   \g<A>|5   \g<B>|6   \g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3   \g<G>))
  (|(?<C>[18]\g<A>|[29]\g<B>|3   \g<C>|4   \g<D>|5   \g<E>|6   \g<F>|[07]\g<G>))
  (|(?<D>5   \g<A>|6   \g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3   \g<F>|4   \g<G>))
  (|(?<E>[29]\g<A>|3   \g<B>|4   \g<C>|5   \g<D>|6   \g<E>|[07]\g<F>|[18]\g<G>))
  (|(?<F>6   \g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3   \g<E>|4   \g<F>|5   \g<G>))
  (|(?<G>3   \g<A>|4   \g<B>|5   \g<C>|6   \g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>))
)
(?<A>$|  [07]\g<A>|[18]\g<B>|[29]\g<C>|3   \g<D>|4   \g<E>|5   \g<F>|6   \g<G>)
于 2013-03-11T06:44:21.267 に答える
5

この問題には別の方法がありますが、これは理解しやすいと思います。ある数を 3 で割ると、0、1、2 の 3 つの剰余ができます。式3t(tは自然数) を使用して、3 で割り切れる数を表すことができます。

余りが 0 の 2 進数の後に 0 を追加すると、実際の 10 進数は 2 倍になります。各桁がより高い位置に移動しているからです。 3t * 2 = 6t、これも 3 で割り切れます。

余りが 0 の 2 進数の後に 1 を追加すると、実際の 10 進数は 2 倍して 1 になります。 3t * 2 + 1 = 6t + 1、残りは 1 です。

余りが 1 である 2 進数の後に 1 を追加する場合。実際の 10 進数は 2 倍プラス 1 になり、余りは 0 になります。 (3t + 1)*2 + 1 = 6t + 3 = 3(2t + 1)、これは 3 で割り切れます。

余りが 1 の 2 進数の後に 0 を追加すると、実際の 10 進数は 2 倍になります。残りは 2 になります (3t + 1)*2 = 6t + 2。

余りが 2 の 2 進数の後に 0 を追加すると、余りは 1 になります。 (3t + 2)*2 = 6t + 4 = 3(2t + 1) + 1

剰余が 2 の 2 進数の後に 1 を追加すると、剰余は 2 のままになります。 (3t + 2)*2 + 1 = 6t + 5 = 3(2t + 1) + 2.

余りが 2 の 2 進数に 1 をいくつ足しても、余りは永遠に 2 です。 (3(2t + 1) + 2)*2 + 1 = 3(4t + 2) + 5 = 3(4t + 3) + 2

したがって、DFA を使用して 2 進数を記述することができます。 3 で割り切れる 2 進数を記述する DFA

注:エッジq2 -> q1には 0 のラベルを付ける必要があります。

于 2015-11-06T20:45:53.217 に答える
2

3 で割り切れる 2 進数は、次の 3 つのカテゴリに分類されます。

  1. 2 つの連続する 1 または 2 つの 1 が偶数の 0 で区切られた数値。事実上、すべてのペアが「キャンセル」されます。

(例: 11、110、1100、1001、10010、1111)

(10 進数: 3、6、12、9、18、15)

  1. 奇数の 0 で区切られた 3 つの 1 を持つ数値。これらのトリプレットは、自分自身も「キャンセル」します。

(例: 10101、101010、1010001、1000101)

(10 進数: 21、42、81、69)

  1. 最初の 2 つのルールの組み合わせ (相互のルールを含む)

(例: 1010111、1110101、1011100110001)

(10 進数: 87、117、5937)

したがって、これら 3 つのルールを考慮した正規表現は次のようになります。

0*(1(00)*10*|10(00)*1(00)*(11)*0(00)*10*)*0*

読み方：

() カプセル化する

* 前の番号/グループはオプションであることを意味します

| | 括弧内のいずれかの側のオプションの選択を示します

于 2016-11-10T02:55:17.017 に答える
1

あなたが直面している問題は、あなたのトリックは（おそらく）有効ですが、実際のDFAにマッピングされないことです（偶数と奇数の数の間の潜在的に任意の違いを追跡する必要があり、任意の数が必要になります州の）。

別のアプローチは、（MSBからLSBまで）i-番目の文字の後x[i]に、モジュロ3演算でサブストリングが0、1、または2に等しくなければならないことに注意することです。この値を呼び出しますS[i]。 x[i+1]0または1のいずれかである必要があります。これは、2を乗算し、オプションで1を加算することと同じです。

したがって、とを知っている場合はS[i]、x[i+1]を計算できますS[i+1]。その説明はおなじみですか？

于 2013-03-11T02:12:41.217 に答える