How do i prove that the regular expression $$a^*(ba^*)^*$$ is the same as $$(a+b)^*$$. Is there a way to prove this using regular expression identities?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Clearly, the second expression generates all strings made of $a$ and $b$.
Now, by induction, with the first expression:
you can generate the empty string $\epsilon$, as $a^0(ba^*)^0$;
any string generated with this expression can be appended with a $b$, which is $(ba^0)^1$;
any string generated with this expression can be appended with a $a$:
either the string is $a^*$, and $a^*a=a^*$,
or the string is $a^*(ba^*)^+$, and $a^*(ba^*)^+a=a^*(ba^*)^*(ba^*)a=a^*(ba^*)^*(ba^*)=a^*(ba^*)^+$.
$\begingroup$
$\endgroup$
My three cents.
Unless I am missing something in the notation, a typical (random) string, ie
$$a^{k_1}b^{k_2}a^{k_3} \dots b^{k_{n-1}}a^{k_n}$$
with $n$ terms and $k_i \ge 0$ arbitrary ($1 \le i \le n$), recognized by the 2nd r.e.
$$(a+b)^*$$
(which I interpret as $(a|b)^*$)
is also recognized by 1st r.e.
$$a^*(ba^*)^*$$
as
$$a^{k_1}(ba^0)^{k_2-1}(ba^{k_3}) \dots (ba^0)^{k_{n-1}-1}(ba^{k_n})$$
and vice-versa, and this covers, without any loss of generality, any string any of the two r.e.'s can recognize. Thus the two regular expressions are equivalent (since they describe the same regular language). QED
Another way to see it is that r.e. $(a+b)^*$ allows one to choose freely between $a$ or $b$ in each iteration during recognizing a string. Similarly r.e. $a^*(ba^*)^*$ allows one the same freedom since any $a$ can be recognized by $a^*$ or $(ba^*)^*$ parts, and any $b$ by $(ba^0)^*$ part.
Finally, a way to transform $(a+b)^*$ into $a^*(ba^*)^*$, and vice-versa, is as follows:
$(a+b)^*$ is equivalent to $a^*(a+b)^*$ for which the second optional term can now start with $b$ (since any leading $a$'s are captured by the first optional term) and followed by any number of $a$'s (which may occur between two $b$'s) and thus is equivalent to $a^*(ba^*)^*$ and vice-versa. QED
