# Regular expression or automata for language with odd number of 0's and odd number of 1's

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?

• Hint, it is regular. Commented Jan 19, 2019 at 0:53

## 1 Answer

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.

• 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 Commented Dec 29, 2018 at 19:16
• There is a mistake, is the product and intersection, not union Commented Dec 29, 2018 at 19:52
• @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. Commented Dec 29, 2018 at 21:04
• 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 Commented Dec 30, 2018 at 8:37