Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Regular expression problem

What is the regular expression for the language 0m1n where m+n is even?

like image 272
erasmus Avatar asked Mar 09 '10 15:03

erasmus


2 Answers

If you mean a string 000...111... where the length of the string is even, you can use ^(00)*(01)?(11)*$

like image 192
SLaks Avatar answered Nov 15 '22 07:11

SLaks


Ok, so you need to consider for zero the cases when there are odd and when they are even. This requires two states, one for even zeros, one for odd zeros. Then for the odd zero case you need to have 1 one then an even number of ones. For the even case you just need an even number of ones.

Its easy to write the DFA, but I don't know how to plot it here, so I'm going to hazard a guess at the regular expression:

(0 (00)* 1 (11)*) \/ (00)*(11)*
like image 38
Il-Bhima Avatar answered Nov 15 '22 08:11

Il-Bhima