Регулярное выражение для строк с четным числом нулей и единиц

Question

Что такое регулярное выражение для строк 0 и 1 с четным числом нулей и четным числом единиц?

У меня есть что-то вроде (1*01*01*)*(0*10*10*)*.

Это выглядит хорошо?

Answer 1

Ну, это, наверное, домашнее задание, но какого черта:

^(00|11|(01|10)(00|11)*(01|10))*$

Редактировать: упрощено!

Answer 2

1100 на языке, но не соответствует вашему выражению. 10101 не на языке, но ваше выражение соответствует этому.

Я бы предложил начать с рисования DFA. Существует довольно очевидная машина с 4 состояниями, которая распознает этот язык. (Можно ли сделать лучше?) Пустая строка на языке, поэтому начальное состояние является принимающим. Есть ли другие принимающие государства? Для непринимающего состояния S есть есть префикс, который берет вас от начала-> S? Есть ли способ вернуться из S обратно в S, не переходя в состояние принятия? Есть ли суффикс, который переводит вас из S в состояние принятия?

Answer 3

Контрпример для заданного вами регулярного выражения: 01010101.

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

Как упоминал Джим Льюис ниже, это действительно должно быть решаемой проблемой.

Answer 4

@tmp = $str =~ /0/g;

print scalar @tmp % 2 == 0 ? 'even' : 'odd';