# Which of the following languages can be represented by regular expressions?

The set of all words contained in $$\{0,1\}^*$$ that have an even number of 0’s and an odd number of 1’s.

I came to discover that it is possible but not sure how. Can anyone express it in a regular expression?

• In my opinion, you're depriving yourself of a good learning experience if you just ask folks how to do it. Why not give it an honest try? Write out an expression, keep trying to invalidate it by making it accept or reject strings that it shouldn't, and come back here with your refined, battle-tested answer.
– Noah
Jul 25 at 14:15

Yes, an easy approach to find a regular expression for mentioned language is:

First, find a regular expression for $$L_{even}=\{w\in \Sigma^*\mid \hspace{6pt}\mid w\mid_0=2k,k\geq 0\}$$ $$=1^*(01^*01^*)^*$$ Next, find a regular expression for $$L_{odd}=\{w\in \Sigma^*\mid\hspace{6pt} \mid w\mid_1=2k+1,k\geq 0\}.$$ $$=0^*1(0^*10^*1)^*0^*.$$ Now let $$L$$ be a language that, contain even number of $$0's$$, and odd number of $$1's$$. Therefore $$L=L_{odd}\cap L_{even}.$$ So we can express $$L$$ as the following regular expression :

$$\left(1\cup 0(00\cup 11)^*(01\cup 10)\right)\left((01\cup 10)(00\cup 11)^*(01\cup 10)\cup (00\cup 11)\right)^*.$$

• Thank you for your immense help. Jul 25 at 15:54
• If the answer is useful, you can accept it.
– Jut
Jul 25 at 16:14
• For me it is difficult to see how the final regex is obtained from the regexes for the two languages using intersection. Jul 26 at 15:52
• I draw the DFA for two languages, then i draw the intersection of two DFAs. Finally i convert our DFA to RE.
– Jut
Jul 26 at 15:58