# Check whether a regular expression is correct

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.

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.