3
$\begingroup$

I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal:

$ (\epsilon + 0^*1^+0)^* = \epsilon + (0+1)^*10 $

here is what I have got so far:

$$ (\epsilon + 0^*1^+0)^* = \\ (0^*1^+0)^* = \\ (0^*1^*10)^* = \\ \epsilon + (0^*1^*10)^+ = \\ \epsilon + (0^*1^*10)(0^*1^*10)^* = \\ \epsilon + 0^*1^*10(0^*1^*10)^*$$

I seem to be stuck, I am not sure if I am doing it the correct way, or if there is a better way to prove this.

I know that $(a+b)^* = (a^*b^*)^* $ is true and I think this will certainly come in handy for the problem above but I am not sure how to prove $(a+b)^* = (a^*b^*)^* $ either.

| cite | improve this question | |
$\endgroup$
0
$\begingroup$

The regular expression on the right consists of the empty word along with all words ending in $10$. All words accepted by the regular expression on the left are of this form. It remains to show that all words accepted by the regular expression on the right are also accepted by the one on the left. This is clear for the empty word, so it remains to show the following:

Every word ending in $10$ is accepted by $(0^*1^+0)^*$.

Indeed, every word ending in $10$ has the form $$ 0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_n} 1^{b_n} 0, $$ where $b_1,a_2,b_2,\ldots,a_n,b_n \geq 1$. We can decompose this word as $$ (0^{a_1} 1^{b_1} 0) (0^{a_2-1} 1^{b_2} 0) (0^{a_3-1} 1^{b_3} 0) \cdots (0^{a_{n-1}-1} 1^{b_n} 0) \in (0^*1^+0)^*. $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ wow did you just come up with that in the 5 seconds after seeing this question? $\endgroup$ – Gravity May 11 '15 at 17:51
  • 1
    $\begingroup$ More or less. When you get more experience you will also be able to solve such questions in no time. I have seen similar questions in the past. $\endgroup$ – Yuval Filmus May 11 '15 at 17:53
  • $\begingroup$ don't know what to say very impressive $\endgroup$ – Gravity May 11 '15 at 17:53
  • $\begingroup$ I'm confused. The question explicitly says "by simplification", which this isn't, but the answer has been accepted. @Gravity, since you seem to be happy with this answer, I suggest you edit your question to remove the restriction. (Perhaps replace it with something like "by some method other than producing and minimizing automata"?) $\endgroup$ – David Richerby May 11 '15 at 20:03
  • $\begingroup$ Alright I will do that, I don't think there is any way to prove it just by simplification, if you find one, my gratitude and vote up will go to you $\endgroup$ – Gravity May 11 '15 at 21:04

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.