Выражение регулярного выражения для нечетного числа а и нечетного числа б

Question

Мне нужно создать регулярное выражение на языке {a, b}, которое принимает всю строку с нечетным числом a и нечетным числом b.

Вот моя последняя и ближайшая попытка:

(((aa+bb)*(ab+ba))*+((ab+ba)(aa+bb)*)*) 

Грейдер говорит, что не удалось "", что, как я полагаю, означает, что он принимает лямбду, но я не понимаю, как.Это не значит, что это единственное, что не так.

Помогите пожалуйста!

Answer 1

У вашей попытки есть несколько проблем:

• Действительно, "" соответствует (и не должно): все части вашего регулярного выражения являются необязательными
• abab, abba, ... и т. д. также будут сопоставлены, потому что ((aa+bb)*(ab+ba))* может совпадать четное число раз.
• То же самое относится ко второй половине регулярного выражения

Вот пример, который бы сработал:

(aa+bb)*(ab+ba)((aa+bb)*(ab+ba)(aa+bb)*(ab+ba))*(aa+bb)*

Здесь первая (ab+ba)part не является обязательным, поэтому "" не будет соответствовать.

Существует четыре состояния, которые необходимо учитывать:

1. четное число a, четное количество b (начальное состояние)
2. четное число а, нечетное число b
3. нечетное число а, четное число b
4. нечетное число а, нечетное число b (целевое состояние)

(aa+bb)* является инвариантом состояния: состояние до совпадения совпадает с состоянием после совпадения.

(ab+ba) меняет состояние 1 на состояние 4 и наоборот (и состояние 2 насостояние 3 и наоборот, но нас это не интересует)

((aa+bb)*(ab+ba)(aa+bb)*(ab+ba))* является инвариантом состояния, но позволяет состоянию переходить в любое другое состояние и в конечном итоге возвращаться к исходному, ...всеми возможными способами.Когда этот шаблон выполняется, начальное состояние равно 4, и поэтому он также выходит в этом состоянии.

Если мы уберем все части, инвариантные к состоянию, останется только (ab+ba), что приведет к переходу в исходное состояниев целевое состояние.

Все допустимые изменения атомного состояния охватываются этим выражением.