Регулярное выражение, совпадающее на основе различий 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)(?!))