regex - 根据二进制字符串中 1's in 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。显然，这至少在理论上是无法实现的(但是，如果 x 的任何前缀中 1 和 0 的数量之差受常数限制，则可以实现)。

这在实践中可能无关紧要，因为几乎每个常见的正则表达式引擎都比正则表达式识别器更强大，但它可能与考试问题的上下文相关。