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

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)

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

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

a(aa)*

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

Answer 4

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

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

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