regex - バイナリ文字列の 1 と 0 の違いに基づいて一致する正規表現

Question

だから、それは最終的な時間であり、私は古い試験でこの問題に出くわしました:

どこを示す正規表現を与えるdiff(x)：

- diff(x) is the number of 1's in x minus the number of 0's in x
- 1 <= diff(x) <= 3

例えば

 diff(10110100111) = 7-4 = 3
 diff(11100011) = 5-3 = 2
 diff(10011) = 3-2 = 1

Answer 1

希望どおりに正規表現を構築することはできないはずです。0^n1^n111もしそうなら、入力とを区別するために、必然的に無制限のカウンターを実装する有限状態オートマトンがあるでしょう0^n1^n1111。少なくとも理論的には、明らかにこれを達成することはできません (ただし、 の接頭辞の 1 と 0 の数の差がx定数によって制限されている場合は達成できます)。

事実上すべての一般的な正規表現エンジンは正規表現認識エンジンよりも強力であるため、実際には無関係かもしれませんが、試験問題のコンテキストでは関連する可能性があります。

Answer 2

対応している正規表現エンジンがわからない場合は、.NET (グループの分散) や PCRE (再帰) などの再帰をサポートするエンジンが必要です。以下は有効であり、.NET で機能します。

^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))