# Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent.
1. http://rubular.com/r/K9Hp9tU6px
2. http://rubular.com/r/N8VpoEcch4
EDIT: Forgot that + was ambiguous here!

I want to prove that the second expression accepts all binary strings, without constructing the equivalent DFAs manually.
Induction comes to mind, but I am probably missing something crucial.
Can anyone of you recommend a few good methods that I can use here?
Also, relevant identities are welcome.
As a generalization of my question here, does a generic pattern for proving "A language is accepted by R1 if and only if it is accepted by R2" exist ?

• Could you rewrite them in Ruby :) I don't follow your syntax. rubular.com – Chad Brewbaker Aug 16 '13 at 15:25
• @ChadBrewbaker: Thanks, didn't consider the ambiguity when typing out..added. – manasij7479 Aug 16 '13 at 15:41
• Take a string $s \in \{0,1\}^*$ and try to prove that it is in $0^*(10^*)^*$. Start with a string $s$ that consists only of zeros. Then try a string that contains a single 1. And so on... – Igor Shinkar Aug 16 '13 at 15:48
• @IgorShinkar: How do I enumerate all the way to 'all possible strings' that way, by choosing specific subsets at a time? – manasij7479 Aug 16 '13 at 15:51
• Don't worry about enumeration. It is enough to prove that any string belongs to $0^*(10^*)^*$. For example, try to understand first why $0010 \in 0^*(10^*)^*$ just get the feeling of what's going on. Then try to see why $001010 \in 0^*(10^*)^*$. Just try a few examples... – Igor Shinkar Aug 17 '13 at 6:29

The identity $$(x + y)^* = x^*(yx^*)^*$$ is a classical identity of regular expressions, but it is a nontrivial problem to find a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob.

J.H. Conway, Regular algebra and finite machines, Chapman and Hall, 1971, ISBN 0-412-10620-5

D. Krob, A complete system of $$\mathcal{B}$$-rational identities. Automata, languages and programming (Coventry, 1990), LNCS 443, Springer, New York, (1990) 60--73. DOI

D. Krob, Complete Systems of $$\mathcal{B}$$-Rational Identities, Theor. Comp. Sci. 89 (1991), 207–343. DOI

• I guess the right hand side of your identity should read $x^*(yx^*)^*$, i.e., $x$ and $y$ be switched underneath the outmost star. As written, for example, it would not match $y$. – StefanH Apr 29 '20 at 11:28