Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I guess $L$ is not regular, but I haven't been able to prove it with the pumping lemma.

If it is not regular, can you give me a hint to prove it?

  • $\begingroup$ Hint, it is regular. $\endgroup$
    – John L.
    Commented Jan 19, 2019 at 0:53

1 Answer 1


Hint: You are trying to solve two problems (i.e., odd number of zeros and odd number of ones) at once. Try to solve each separately instead and then combine the solutions appropriately.

  • $\begingroup$ So, solving each separately, doing the product of both automatas and taking as final states those which were final states in the single problem, isn't it? I mean, the union of both automatas $\endgroup$ Commented Dec 29, 2018 at 19:16
  • $\begingroup$ There is a mistake, is the product and intersection, not union $\endgroup$ Commented Dec 29, 2018 at 19:52
  • $\begingroup$ @vicase98 In the case of automata, yes, you want the intersection. (And the construction is fairly straightforward.) In the case of regexes, it is a bit more intricate, unfortunately. $\endgroup$
    – dkaeae
    Commented Dec 29, 2018 at 21:04
  • $\begingroup$ Once I have the automata, I can get the regular expression. It's tedious, but algorithmic. Thank you for your help, I voted your response, but It doesn't appear until I have a specefic reputation $\endgroup$ Commented Dec 30, 2018 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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