Converting a regular expression to an automaton

Let’s see how to convert any regular expression to a non-deterministic finite automaton.

Example

Before we describe the algorithm itself, let’s look at an example to see what we are aiming for. Take this regular expression: a(b|c)x^∗. In words, the language generated by the regular expression consists of the strings that start with the letter “a”, followed by either “b” or “c”, and then any number of the letter “x”. Could we build an automaton that accepts this language? Sure, take a look:

This automaton clearly accepts the same language. That raises the question of whether, for every regular expression, there is an automaton that accepts the language it generates. Well, yes.

The algorithm for converting a regular expression to an automaton

Suppose the input is a regular expression R. From the earlier section on regular expressions we know that a regular expression can take six different forms. So we distinguish six cases:

1. R = a for some symbol a ∈ Σ. So the regular expression is just a single symbol from the alphabet Σ we are working over. An automaton that accepts a single symbol a would look like this:

   

2. R = ϵ, the empty string. An automaton that accepts the empty string would look like this:

   

3. R = ∅, a regular expression that generates the empty language. An automaton that recognises such a language is this one:

   

4. R = R₁ ∪ R₂, where R₁, R₂ are regular expressions. We already know that the union of regular languages is again a regular language and that we can build an automaton that accepts such a language. In other words, we assume we have automata that recognise the languages generated by R₁ and R₂, and we use them to build an automaton that accepts the language generated by R₁ ∪ R₂. For example, if R₁ = a and R₂ = ϵ, the procedure gives us this automaton:

   

5. R = R₁ ∘ R₂, where R₁, R₂ are regular expressions. This is the same situation as in the previous point. The concatenation of regular languages is a regular language, so we can build an automaton that accepts it. So if R₁ = a and R₂ = b, the concatenation would look like this:

   

6. $R=(R_1^{\ast })$, where R₁ is a regular expression. Again, we know that the closure of a regular language is a regular language. So if R = a^∗, the automaton would look like this:

   

By applying these cases repeatedly, we convert the whole regular expression to a finite automaton.

A complete example

Let’s try converting the regular expression (a|bc)^∗. Step by step, we get these automata:

This final automaton accepts the language generated by the regular expression (a|bc)^∗. Of course, the automaton is insanely complicated and there is certainly a much simpler automaton that accepts the same language. We can use the algorithm for converting an NFA to a DFA and then carry out DFA minimisation.

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools