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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – 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)^*.$$

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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .