3
$\begingroup$

I have $L_1=\{b^*+b^*a(b+ab^*a)^*ab^*\}$ and $L_2=\{(b^*ab^*a)^*b^*\}$. I want to prove or disprove that they are equivalent.

I have proved that $L_2\subseteq L_1$ and I tried to transform the second expression in $L_1$ in order to find an expression contained in $L_2$ (without any luck so far). I tried also to find a word in $L_1$ that doesn't belong to $L_2$, but didn't have any luck either (all where in it).

Could anyone help?

$\endgroup$

1 Answer 1

5
$\begingroup$

It's hard to give hints without solving the problem for you. Some general hints:

  • When working with regular expressions, the $^+$ sign ("one or more") is a useful shorthand:

    $X^+ = XX^* = X^*X$

    $X^* = \epsilon \cup X^+$

    For instance, in this case, we can write:

    $L_1 = L(b^*+b^*a(b+ab^*a)^*ab^*) = L(b^*) \cup L_3$ $L_2 = L((\epsilon+(b^*ab^*a)^+)b^*) = L(b^*+(b^*ab^*a)^+b^*) = L(b^*) \cup L_4$, with $L_3 = L(b^*a(b+ab^*a)^*ab^*)$ and $L_4 = L(b^*ab^*a)^+b^*)$,

    and since all members of $L_3$ and $L_4$ contain an $a$, $L_1 = L_2$ only if $L_3 = L_4$.

  • Expand the expressions into disjunctive form, $X_1 + X_2 + \ldots$, such that the subexpressions are, either:

    • the shortest strings in the language, or
    • expressions that only generate longer strings.

    Your hope is to quickly find, either:

    • a string that is in one and not the other, or
    • some kind of recurrence relation proving that they are $=$ or $\subseteq$.
  • No finite set of rewrite rules suffices to rewrite all equivalent regular expressions into each other. So you may fail to find a successful rewriting even when the expressions describe the same language.

  • When rewriting or finding a proof by induction, consider using not only regular expressions, but also set-theoretic descriptions of languages ("the language such that ...") and properties defined in such terms.

    For instance, above I used the property that languages $L_3$ and $L_4$ are such that all of their strings contain an $a$.

If all else fails: a completely rigorous method to prove or disprove equivalence of regular expressions is to convert them to NFAs, then to minimal DFAs: two regular expressions are equivalent if and only if the resulting minimal DFAs are isomorphic. However, both conversion steps may cause an exponential blowup in size.

$\endgroup$
1
  • 1
    $\begingroup$ An excellent answer! A couple of things that I would add: 1) Showing that $L_1 \subseteq L_2$ is also possible using all of these methods. 2) DFA minimisation is roughly the same algorithmic effort as showing that two DFAs accept the same language, so it probably makes sense to do that directly. You can also do the same algorithm without explicitly constructing any automata by using Brzozowski derivatives. $\endgroup$
    – Pseudonym
    Commented Jun 21, 2023 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.