Proving following regular expressions equal to one another?

Question

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to one another because the second $( a + b )^*$ is a redundant term as the expression will always have an $ab$ together. But how can I formalize this and show, in general, that this is true ?

Answer 1

The general method is to convert the two regular expressions to a finite automaton each and compare those.

In detail:

• Convert a regular expression to a non-deterministic finite automaton (NFA), e.g. via Thompson's construction
• Convert a NFA to a deterministic finite automaton (DFA) via power set construction
• Apply DFA minimization to a given DFA to get a unique DFA.

Here we might get away with naming \begin{align} L_1 &= (a+b)^* a (a+b)^* b (a+b)^* \\ L_2 &= (a+b)^* ab (a+b)^* \end{align} and first noting $$ L_1 \supseteq L_2 $$ as the middle part $(a+b)^*$ of the $L_1$ contains the empty word $\epsilon$.

For equality we need to show $$ L_1 \subseteq L_2 $$ as well. Let $w = xuy \in L_1$, such that $u$ is accepted by the middle part $(a+b)^*$. Obviously $u \in \{a,b\}^*$.

If $u = \epsilon$ then $w = xy \in L_2$, as $x \in (a+b)^*a$ and $y \in b(a+b)^*$.

Otherwise we assume $u = bu'$ with $u' \in \{a,b\}^*$. We note that $y'= b u' y \in b(a+b)^*$. So we have $w = xy' \in L_2$

Else $u = au'$ with $u' \in \{a,b\}^*$ then $x'=xa \in (a+b)^*a$ as well and we could consider the smaller problem instance $u'$ for $w=x'u'y$. As $u$ was finite, we will end up in the first case, if $u$ consisted of $a$ symbols only, or with a reduced $u = bv$, thus the second case.

This showed that $L_1 \subseteq L_2$ together with the initial $L_1 \subseteq L_2$ we claim equality $L_1 = L_2$.

Answer 2

It depends on how formal you want to be. Letting the two languages be $L_1$ and $L_2$, I’d take it as evident that $L_2$ is the set of words over $\{a,b\}$ that contain $ab$ as a subword. It’s also clear that $L_1\supseteq L_2$, since $a(a+b)^*b$ generates $ab$. Thus, it suffices to show that $L_1\subseteq L_2$, which can be done by showing that every word generated by $a(a+b)^*b$ contains $ab$ as a subword.

This is quite easy. Suppose that $w$ is generated by $a(a+b)^*b$. Let $w=c_1\ldots c_n$, where $c_k\in\{a,b\}$ for $k=1,\ldots,n$, $c_1=a$, and $c_n=b$; clearly $n\ge 2$. Let $m\in\{1,\ldots,n-1\}$ be maximal such that $c_m=a$; then $c_{m+1}=b$, and $w=xaby$ for some $x\in\{a,b\}^*$ and $y\in\{b\}^*$, as desired.

Answer 3

There's a method that's simpler than dealing with NFA's. Brzozowski's method of regular expression derivatives (see this paper) constructs a DFA for any regular expression, and it handles booleans nicely. So, given two regular expressions $r_1$ and $r_2$, you can apply Brzozowski's construction to get a DFA for $r_1 \wedge \lnot r_2$ (to see what's matched by $r_1$ but not $r_2$) or even $r_1\iff r_2$ to see if they're equivalent. Once you have the DFA it's a quick depth-first search to see whether any accept states can be reached, but it can be easier than that. I just ran the algorithm on your examples to get a DFA for the regex $(r_1\wedge\lnot r_2)\vee(r_2\wedge\lnot r_1)$, the symmetric difference. The DFA returned had no accept states, so $r_1$ and $r_2$ are equivalent.