I need to construct a regular expression using language {0,1}
The regular expression should accept odd number of 0's and odd number of 1's
See Question&Answers more detail:osI need to construct a regular expression using language {0,1}
The regular expression should accept odd number of 0's and odd number of 1's
See Question&Answers more detail:osThe whole regex:
^((00|11)*(10|01)(00|11)*(10|01)(00|11)*|(00|11))*(10|01)((00|11)*(10|01)(00|11)*(10|01)(00|11)*|(00|11))*$
A way of conceptualizing it:
x = (00|11)
y = (10|01)
z = x*yx*yx*
^(z|x)*y(z|x)*$
Because we are thinking about parity, and not counting, this can be done in regex. The pattern x
does not effect parity, while the pattern y
switches parity. The pattern z
looks for matching y
(net effect of zero on parity), ignoring intervening x
. Then you just need one y
.
Perhaps a shorter regex, using y
to match the last switch of parity, may be:
^(z|x)*yx*$
^(x*yx*yx*|x)*yx*
Which is:
^((00|11)*(10|01)(00|11)*(10|01)(00|11)*|(00|11))*(10|01)(00|11)*$
This has not been tested extensively, but I believe it works.