regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

Question

$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, then i used FSM2Regex which gave me $r_3$ which i simplified into $r_2$ using regex simplifier.
now $r_2$ seems better than $r_1$. Should I go with it? If so, what is lacking in $r_1$? I can't see the difference between $(a+b)^*b$ from $r_1$ and $(aa^*b)^*$ from $r_2$. Is one the subset of other? Are they overlapping or disjoint?

Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's especialy because for some reason that is beyond me, it also draws $\$$ (null string) transitions. Even $r_3$ doesn't give back the FA I used to generate it. So my question is : are $r_1$ and $r_2$ different? How? what should I go with?

Answer 1

Yes, the regular expressions $r_1=\Lambda+(a+b)^*b$ and $r_2=(b+aa^*b)^*$ are equivalent. There are several ways of doing this.

1. Just observe that both of them match the empty string and all strings ending with $b$.

2. Convert them to automata and then produce automata for $L(r_1)\setminus L(r_2)$ and $L(r_2)\setminus L(r_1)$. Minimize both automata and find that they both accept the empty language. (Actually, you'll find that you make a ton of mistakes and at least one of the automata accepts something, and at least one of the minimizations is wrong. But, if you were a computer, this wouldn't be an issue.)

3. Clearly both regular expressions match the empty string, so let's show that they match the same non-empty strings, too. Suppose that $w\in L(r_2)\setminus\{\Lambda\}$. Then we can write $w=w_1\dots w_\ell$ where each $w_i$ is a string that either matches $b$ or $aa^*b$. In particular, $w_\ell$ must match one of these things, so the last character of $w_\ell$ is a $b$, so $w\in L(r_1)$.

   Conversely, suppose that $w\in L(r_1)\setminus\{\Lambda\}$. Write $w=s_1\dots s_n$, where each $s_i\in\{a,b\}$. Suppose there are $\ell$ $b$s in $w$ and let these be at positions $p_1, \dots, p_\ell$. Because $w\in L(r_1)$, $p_\ell=n$ (the last character is $b$). For convenience, let $p_0=1$. We can now write $w=w_1\dots w_\ell$, where $w_i=s_{p_{i-1}+1}\dots s_{p_i}$. For each $i\in\{1, \dots, \ell\}$, we have $w_i=a^{p_i-p_{p-1}-1}b$, so each $w_i$ matches either the regular expression $b$ or $aa^*b$. Therefore, $w$ matches $(b+aa^*b)^*= r_1$.

By the way, a fourth equivalent regular expression is $(a^*b)^*$, which you can see by observing that the inner part of $r_1$ is equivalent to $b+a^+b$, which is $a^*b$.