Регулярное выражение, определяющее обычный язык с {a, b} без подстроки с ровно 3 b (bbb)

Question

В значительной степени то, что говорит вопрос.Я придумал

(ba)?(a + bb + bbbbb + aba)*(ab)?

Есть что-нибудь более читабельное?Или это неверно?Я знаю, что вы не должны делать такого рода вещи с Regex, когда можете просто зайти! ~ / Bbb / в своем коде, но это теоретическое упражнение.

Спасибо.

Редактировать для уточнения: я не использую | для представления бита ИЛИ в регулярном выражении и вместо него использую +.Извините за путаницу.

Редактировать 2: {a,b} для языка только с символами «a» и «b».Не {минимум, максимум}.Прости еще раз.

Редактировать 3: Поскольку это часть теоретического класса, мы просто имеем дело с основами Regex.Единственное, что вам разрешено использовать, это +,?, () И *.Вы не можете использовать {минимум, максимум).

Answer 1

Я думаю, что у меня есть работающее регулярное выражение.Пусть b° - это нотация, которую я только что изобрел - будет регулярным выражением, которое соответствует нулю или большему числу b, за исключением того, что оно не совпадет с тремя из них.Это может быть заменено на (ε | b | bb | bbbb+), так что не беспокойтесь, что я использую магию или что-то еще.Теперь я думаю, что совпадающие строки можно рассматривать как повторяющиеся подшаблоны с нулями или более a, за которыми следует b°, что может быть (a*b°)*, но вам нужно, чтобы между последовательностями b была хотя бы одна буква "a".Таким образом, ваше последнее регулярное выражение равно a*b°(a+b°)*.

Поскольку b° может соответствовать пустой строке, начальное значение a* является излишним, поскольку a+ может подобрать начальное значение a просто отлично, поэтому регулярное выражение можетбыть оптимизирован до b°(a+b°)* (спасибо, wrikken).

Answer 2

Хм, как то так?

^(a|(?<!b)b{1,2}(?!b)|b{4,})*$

редактировать

Редактировать 3: Поскольку это часть теоретического класса, мы просто имеем дело с основами Regex. Единственное, что вам разрешено использовать, это +,?, () И *. Вы не можете использовать {минимум, максимум).

Пффф, говорим о связывании рук за спиной ... Простое решение: вы не можете этого сделать (^ & $ являются требованиями , чтобы это когда-либо работало), и нам нужен |. Итак, придумайте лучшие условия. Отбросить взгляд назад и смотреть вперед можно сделать , но это не будет красиво (по крайней мере, не без нарушения DRY):

^(b|bb|bbbb+)?(a+(b|bb|bbbb+)?)*$

Answer 3

Вы соответствуете строке без точно 3 б подряд. Это означает, что вы смотрите на подстроки типа "aa", "aba", "abba" и "abbbbb * a", где любой из внешних a может быть началом или концом строки, может перекрываться и может быть множественным. Это предполагает что-то вроде:

(a + ab + abb + abbbbb*)*

с соответствующими дополнениями для учета пропущенного a в начале строки. Здесь много повторений, но именно так регулярные выражения работают в базовой форме.