So,
I'm working through some proof exercises, and one of the questions is about the following regular expression: (a|b)* = a*(a|b)*
- if they are equivalent, prove that it is so
- if they are not, provide a counter example
I'm sure that they're equivalent, and can explain why, but I do not think it qualifies as a formal proof. (there can be zero as in the left side, so that it becomes (a|b)* = (a|b)*).
I am familiar with inductive proofs and other proof methods, but only for proving things like, if a number is even, or for equations. I'm not sure how to begin to apply it to regular expressions (specifically, the "zero of more" part).
Could you please help me work through the steps of a formal proof for this?
Thank you.
To prove equality of regular expression you ave to prove the equality of their language hence a double inclusion.
Your intuition "there can be zero $a$'s in the left side" only give you the inclusion $L((a|b)^*)\subseteq L(a^*(a|b)^*)$ since you can match any word of $(a|b)^*$ with the regular expression $a^*(a|b)^*$ by matching $\epsilon$ with $a^*$.
For the other inclusion you can say that $a^*$ is a restriction of $(a|b)^*$ hence anything that is matched by $a^*$ can by matched by $(a|b)^*$ hence $L(a^*)\subseteq L((a|b)^*)$ hence $L(a^*(a|b)^*)\subseteq L((a|b)^*(a|b)^*)=L((a|b)^*)$.
If you want to perform an induction you can do it as follow.
Let $P(n)$ be: "all word $w$ of size $n$ is recognized by $(a|b)^*$ iff it is recognized by $a^*(a|b)^*$.
Base case: $n=0$. The only word of size $0$ is $\epsilon$ recognized by both the regular expressions. Hence $P(0)$ is true.
Assume that $P(n)$ hold. We show that $P(n+1)$ is also true. Let $w$ be a word of size $n+1$.
Assume that $w$ is recognized by $(a|b)^*$ hence $w$ is of the form $w'a$ or $w'b$ with $w'$ a word of size $n$ recognized by $(a|b)^*$. By hypothesis $w'$ is recognized by $ a^*(a|b)^*$ thus the added $a$ (or $b$) can be matched by $(a|b)^*$ thus $w$ is also recognized by $ a^*(a|b)^*$.
Assume now that $w$ is recognized by $a^*(a|b)^*$ hence $w$ is of the form $w'a$ or $w'b$ with $w'$ a word of size $n$ recognized by $a^*(a|b)^*$. The same argumentation gives you that $w$ is recognized by $(a|b)^*$. Hence $P(n+1)$ is true.