Можно ли еще упростить это регулярное выражение?

Question

Я работаю над домашней работой для своего класса компилятора, и у меня следующая проблема:

Напишите регулярное выражение для всех строк a и b , которые содержат нечетное число a или нечетное число b (или оба).

После большой работы с доской я придумал следующее решение:

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

Однако, это самое простое, что я могу получить? Я подумывал о создании DFA, пытаясь свести к минимуму количество состояний, чтобы посмотреть, поможет ли это мне упростить, но я решил, что сначала я бы попросил гуру регулярных выражений в SO.

Answer 1

Примите рекомендацию Грега Ди, начиная с (аа) * и переходя оттуда. Sepp2k почти все правильно, но реальное соображение заключается в том, что вас не волнует другое письмо. Я имею в виду, что когда вы смотрите на ограничение «нечетное число а», вас совершенно не волнует, что б есть в вашей строке. Таким образом, придерживайтесь b * везде, где вы можете:)

Ответ Sepp2k почти правильный, но этот правильный:

b* a b* (a b* a b* )* | a* b a* (b a* b a* )*

Чтобы уточнить, это регулярное выражение вычисляет все строки с нечетным числом a (первый раздел), а OR - эти строки с любыми строками, содержащими нечетное число b.

Answer 2

Это должно работать:

b* a b* (a b* a b*)* |  a* b a* (b a* b a*)*

Answer 3

Боюсь, что я не верю, что ваше регулярное выражение, как написано, правильно. Рассмотрим строку:

aba

У нас есть пара вариантов для матчей, но тот факт, что это нечетная длина, означает, что мы должны соответствовать одиночному a спереди, поэтому:

(a)(ba)

Но, к сожалению, ваша вторая основная группа не может соответствовать (ба).

При работе с таким ограничением я обнаружил, что легче начать с основного ограничения и перейти оттуда. В этом случае ваше ограничение "нечетное", поэтому начните с

a(aa)*

, чтобы вызвать нечетное число a и перейти оттуда. :)

Answer 4

Я думаю, вам нужно по-другому подойти к проблеме.

Вы пытаетесь сопоставить все, что не имеет четных чисел a и b.

Вероятно, было бы легче начать с чего-то, что соответствует даже числам a и b. Все, что вам нужно сделать в этот момент, это добавить что-то в конце, соответствующее наименьшей строке, которую вы действительно хотите сопоставить.