Проблема регулярного выражения

Что такое регулярное выражение для языка 0 m1n где m+n четно?

2 6
regex regular-language

2 ответа:

Если вы имеете в виду строку 000...111..., где длина строки Четна, вы можете использовать ^(00)*(01)?(11)*$

14

Хорошо, поэтому вам нужно рассмотреть для нуля случаи, когда есть нечетные и когда они четные. Для этого требуется два состояния: одно для четных нулей, другое для нечетных нулей. Тогда для нечетного нулевого случая вам нужно иметь 1 единицу, а затем четное число единиц. Для четного случая вам просто нужно четное число единиц.

Его легко написать DFA, но я не знаю, как построить его здесь, поэтому я рискну предположить регулярное выражение: 

(0 (00)* 1 (11)*) \/ (00)*(11)*
1