Регулярное выражение для равного числа 0 и 1

regex

8201 просмотра

4 ответа

Как найти регулярное выражение с равным числом 1 и 0. Меня также интересует, как вы думаете, такое решение?

пример: должен соответствовать: 1100, 00100111, 01. не должно совпадать: 110, 0, 11001.

Мне нужно регулярное выражение, которое дает множество всей такой строки. Если длина строки в множестве задана регулярным выражением, 2nто число 0sдолжно быть равно числу 1s = n.

Источник Размещён: 12.11.2019 09:02

Ответы (4)


8 плюса

Невозможно сгенерировать регулярное выражение для языка L = (0,1) (одинаковое количество единиц и нулей). Это не обычный язык, поэтому его нельзя описать с помощью регулярного выражения. Это не регулярно, потому что автомату, который принимает его, потребуется различное количество памяти в зависимости от длины ввода. Обычный язык - это тот, который использует постоянную память, независимо от длины ввода. Язык, который вы описываете, может генерироваться контекстно-свободной грамматикой, но не регулярным выражением. Следующий CFG генерирует строки, в которых числа 0 и 1 равны. Если S - любое слово в языке: S -> SS; S -> 0S1; S -> 1S0; S -> e пустое слово Для этого языка вам нужен стек, и для его принятия может быть разработан автомат для восстановления или машина Тьюринга.

Автор: LucieCBurgess Размещён: 18.05.2016 10:59

3 плюса

Невозможно с обычной грамматикой (конечный автомат): http://en.wikipedia.org/wiki/Regular_language

Автор: Nahuel Fouilleul Размещён: 19.09.2012 03:24

3 плюса

Вот шаблон регулярных выражений для движка .NET, который удовлетворяет ваши потребности. Посмотрите это в действии на ideone.com .

^((?(D)(?!))(?<C>1)|(?(D)(?!))(?<-C>0)|(?(C)(?!))(?<D>0)|(?(C)(?!))(?<-D>1))*(?(C)(?!))(?(D)(?!))$

Он работает с использованием двух стеков, используя один (C), если количество единиц больше, чем 0, и другой (D), если больше нулей, чем единиц.

Не красиво, определенно не пригодно для использования, но это работает. (Ха!)

Автор: Jens Размещён: 12.02.2013 03:36

1 плюс

Хотя это невозможно с обычной грамматикой, как указано в другом ответе, должно быть относительно легко сканировать строку, увеличивать счетчик для каждого 1и уменьшать его для каждого 0. Если конечное число равно 0, то число 0s и 1s равно (по модулю 2 ^ wordsize - наблюдение за переполнением сделает его немного сложнее, но в зависимости от того, есть ли другие предположения, которые могут быть сделаны относительно ввода, что может не понадобиться).

Автор: twalberg Размещён: 19.09.2012 03:41
Вопросы из категории :
32x32