I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof).
The process is to show that R1 is a subset of R2, and then show R2 is a subset of R1. I'm a bit stuck on moving forward with my problem. Any help would be sweet.
$R_1 = \epsilon + (0+1)^{*}1$
$R_2 = (0^{*}1)^{*}$
Thanks!
Best Answer
Hint: Show that any string that follows the spec of $R_1$ lies in $R_2$, and vice versa.
Another hint: $R_1$ clearly describes the set of all strings that end with $1$, plus the empty string. Now show that (a) all strings in $R_2$ have this property, (b), every such string can be written in a form that shows that it belongs to $R_2$.