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 ?