Prove equivalence of two regular expressions.

491 Views Asked by At

I am wondering if there is a standard way to prove that two regular expressions are equivalent. I have tried to prove, given two regular expressions $r$ and $s$, that $L(r) \subseteq L(s)$ and $L(s) \subseteq L(r)$ where $L(r)$ is the language accepted by $r$ and the same with $L(s)$ but I have got stuck, I think this aproach is hard. Can you give some tips or strategies?

1

There are 1 best solutions below

0
On

Sometimes you can get by logic $L(r)$. Then you can prove that it is also $L(s)$.

Sometimes you can use regular expressions identifies, like: $$(a+b)*a* = (a+b)*$$ There is more here.

It is hard to tell more without specific example of regular expression.

EDIT:

In your example you can show that both r and s are "words ends by b". It is easy to show that any word in r and in s ends by b. It might be quite harder to show that all words ends by b contained in r, but it can be done by separating the word to subwords which all ends by b.