6
$\begingroup$

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what approach can I use?

If it helps, you can assume the language is given in English (e.g., something like "$L$ is the set of words that contain at least one $a$, an even number of $b$'s, and does not contain the substring $ab$") or algebraically (e.g., $L=\{a^i b^j (abb)^k : i+2j+k=3\ell, i,j,k,\ell \in \mathbb{N}\}$).

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ How is your language given? $\endgroup$
    – J.-E. Pin
    Commented Aug 26, 2015 at 4:53
  • $\begingroup$ @J.-E.Pin, see revised question. One possible goal is to have a reference that will typically be sufficient for most people who come here with an exercise from their formal languages book (here's this language, how do I find a regexp for it), so if you've seen those kinds of exercises, you've probably seen how the languages are typically specified in them. Was there some answer you were especially hoping for? You're welcome to edit if you think there's a different set of assumptions that make more sense. $\endgroup$
    – D.W. ♦
    Commented Aug 26, 2015 at 16:02
  • $\begingroup$ I struggle not so see this as redundant to this one. $\endgroup$
    – Raphael
    Commented Sep 3, 2015 at 8:47
  • $\begingroup$ @Raphael, me too! To me, the relationship is obvious. But apparently, to others, the relationship is not obvious. See e.g., this example and this example (cont.) $\endgroup$
    – D.W. ♦
    Commented Sep 3, 2015 at 16:50
  • $\begingroup$ and this example. Anyway, I wouldn't have any complaints if this were closed as a dup of that reference question -- feel to do so if you see it as a dup. (For instance, we could still use this as a dup target for closing questions that are a problem dump of their "find a regular expression for this language" exercise.) $\endgroup$
    – D.W. ♦
    Commented Sep 3, 2015 at 16:51

2 Answers 2

Reset to default
4
$\begingroup$

Occasionally you can just stare at the language, get insight, and write down a regular expression just like that. However, more typically, we need a systematic procedure. Fortunately, the field of formal languages provides a more systematic approach that will help you structure your approach to this problem. Often, one effective approach is as follows:

Step 1. Find a non-deterministic finite-state automaton (NFA) for the language.

Step 2. Convert the NFA to a regular expression.

Step 3. Double-check whether your regular expression is correct.

In more detail, here is how you do each of those two steps:

Step 1. To find a NFA for your language, you can think of this as a programming problem, where you have to write a program that works in a very limited programming language where you are only allowed to have a fixed, finite amount of state. Try to write a program that reads in a string one letter at a time and decides whether the input string belongs to the language or not, using only a fixed amount of memory (say, $c$ memory cells, where $c$ is some constant that does not depend on the input string, not even on the length of the input string). This program then corresponds naturally to a NFA, where the NFA has one state per possible value of the program's memory.

Sometimes, it can also be helpful to use the closure properties of NFA. For instance, if the language $L$ is specifies as $L = L_1 \cup L_2$, then it suffices to build a NFA for $L_1$ and a NFA for $L_2$; then the closure properties for regular languages allow you to derive a NFA for $L$. For more techniques to build a NFA, take a look at our reference question How to prove a language is regular? for more approaches.

Step 2. To convert the NFA to a regular expression, apply the algorithm described in How to convert finite automata to regular expressions?.

Step 3. To check whether your regular expression seems to be correct, you can try testing it on a few example strings to see if it seems to give the correct answer. Try both several examples that are in the language and several that are not.

This is just one approach. There are other approaches, including writing down a regular grammar and converting it to a regular expression, or writing a system of linear expressions in regular languages and converting to a regular expression using Arden's Lemma, or others. For an overview of those methods, take a look at How to prove a language is regular?, How to convert finite automata to regular expressions?, and Known algorithms to go from a DFA to a regular expression.

You can also look at other examples of this kind of problem on this site, e.g., by looking at questions tagged .

Improve this answer
$\endgroup$
1
  • $\begingroup$ While correct, this is disappointing standing alone: since regular languages are often defined via regular expressions (i.e. inductively), one should hope that there are patterns/heuristics that allow to come up with one directly. (Myself, I think I'd always go via automata. I think I have a useful answer in that vein, but that should probably go to the "how to prove regular" question?) $\endgroup$
    – Raphael
    Commented Sep 3, 2015 at 8:43
-1
$\begingroup$

What @D.W. has not mentioned is how exactly to construct an automaton based on a language. This can be achieved in polynomial time using Angluin's Theorem.

Improve this answer
$\endgroup$

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.