Разве порядок не имеет значения в регулярных выражениях?

Question

Я смотрел на вопрос, заданный в этой ссылке на стек-поток ( Регулярное выражение для нечетного числа ), для которого его просят найти регулярное выражение для строк с нечетным числом a сверхΣ = {a,b}.

Ответ, данный верхним комментарием, который работает: b*(ab*ab*)*ab*.

Я совершенно сбит с толку - a был помещен непосредственно перед последним b*, действительно ли этот порядок имеет значение? Почему это не может быть b*a(ab*ab*)*b* вместо этого (где a ставится после первого b*), или любая другая его перестановка?

Еще одна вещь, которая меня смущает, это почему (ab*ab*)* а не (b*ab*ab*)*. Разве b*ab*ab* не является более точным определением «иметь ровно 2 a»?

Answer 1

Почему это не может быть b*a(ab*ab*)*b* вместо этого?

b*a(ab*ab*)*b* не работает, потому что это потребует, чтобы строка имела два последовательных a s перед первым неведущий b, не так ли? Например, abaa не будет соответствовать предложенному вами регулярному выражению, когда это необходимо. Используйте отладчик регулярных выражений на таком сайте, как Regex101 , чтобы убедиться в этом сами.

С другой стороны, перемещение всей ab* части в начало (b*ab*(ab*ab*)*) также работает.

почему это (ab*ab*)*, а не (b*ab*ab*)*?

(b*ab*ab*)* работает , но первый b*довольно избыточно, потому что все, что осталось b, будет соответствовать последнему b* в группе. Также перед группой стоит b*, что приводит к тому, что b* не может ничего сопоставить, следовательно, это избыточно.

Answer 2

Существует бесконечно много эквивалентных регулярных выражений, которые порождают данный (бесконечный) регулярный язык. Отдельное выражение может быть предпочтительным в некоторых случаях и некоторыми авторами: кто-то может предпочесть минимальное выражение, или выражение, которое показывает структуру или симметрию, или даже такое, которое упрощает рассуждение в доказательстве по индукции.

Ваш конкретныйпредложение переместить a недостаточно, поскольку, как отмечалось выше, это гарантирует, что подстрока aa появится в любой строке с более чем одним a. Тем не менее, ab ab можно изменить на b ab a, чтобы сделать это размещение работоспособным. Выбор b ab ab * подойдет для любого размещения. Вы могли бы даже пойти для выражения как b ab + b ab ab ab + (b ab ab *) a (b *)1017 * ab ab *), с которым может быть приятно работать в зависимости от вашего приложения. Нечто подобное b * (ab ab ) ab * имеет преимущество в том, что оно минимально (если оно не строго минимально, оно должно быть довольно близко).