0
$\begingroup$

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?

$\endgroup$
1
  • 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, 2021 at 14:15

1 Answer 1

1
$\begingroup$

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)^*.$$

$\endgroup$
4
  • $\begingroup$ Thank you for your immense help. $\endgroup$ Jul 25, 2021 at 15:54
  • $\begingroup$ If the answer is useful, you can accept it. $\endgroup$
    – Jut
    Jul 25, 2021 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, 2021 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, 2021 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.