0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint, it is regular. $\endgroup$ – John L. Jan 19 '19 at 0:53
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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$ – vicase98 Dec 29 '18 at 19:16
  • $\begingroup$ There is a mistake, is the product and intersection, not union $\endgroup$ – vicase98 Dec 29 '18 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 Dec 29 '18 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$ – vicase98 Dec 30 '18 at 8:37

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.