Check whether a regular expression is correct

Question

I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?

I know that there can be multiple regular expressions that are correct.

^{This is intended as a reference we can point others to. Please explain your method in a form that someone new can understand it.}

Answer 1

Yes. It depends how the regular language $L$ is specified. I describe below an algorithm for this problem, i.e., a systematic procedure that you can follow to check correctness. You can simulate running such an algorithm by hand, with pencil-and-paper, if necessary: it might be tedious, but it works. Even better yet, you can implement it on a computer and let the computer run the algorithm.

As a finite automaton

If the language $L$ is provided in the form of a finite automaton (e.g., DFA or NFA), then there are standard algorithms to check whether the NFA/DFA is equivalent to $L$, i.e., whether they generate the same language.

1. If you have a NFA for $L$, first convert it to a DFA for $L$ (e.g., using the subset construction). If it is already a DFA, you can skip this step.
2. Then, convert the regular expression $R$ to a NFA (e.g., using Thompson's algorithm, or using Brzozowski derivatives) and convert the NFA to a DFA. Or, you can see https://cs.stackexchange.com/a/13606/755 for details on how to convert a regular expression to a DFA.
3. Minimize both DFA (see https://en.wikipedia.org/wiki/DFA_minimization).
4. Finally, check whether the two minimal DFA are isomorphic, i.e., are the same, after relabelling of states. If they are the same, then the regular expression $R$ is correct. If they are not the same, then the regular expression is incorrect -- and moreover, you can identify a specific word that is accepted by one DFA and not by the other, and thus which demonstrates that $R$ is not a correct regular expression.

See also How do I verify that a DFA is equivalent to a NFA?, as well as Is there a way to test if two NFAs accept the same language? if you are implementing this in practice.

As a regular expression

If $L$ is described by providing a regular expression, then test whether the two regular expressions are equivalent. See Algorithm to determine whether two regexes are equivalent for a detailed description of how to do that. (Related: https://cs.stackexchange.com/a/52860/755.)

Provided in some other way

If the language $L$ is specified in some other way, you can first find a finite automaton for it (see How to prove a language is regular?) or find a regular expression for it (see How do I find a regular expression for a particular language?), then apply the above methods.

Other approaches

There are other methods as well. See, e.g., Proving Equivalence of Two Regular Expressions for description of other methods that might be easier in some circumstances.