From Regular Expressions to Automata #

The regular expression is the notation of choice for describing lexical analyzers and other pattern-processing software. However, implementation of that software requires the simulation of a DFA.

In this section we shall first show how to convert regular expressions to NFA's using Thompson's construction. Next, we show how to convert NFA's to DFA's using the subset construction.

From a Regular Expression to an NFA #

Consider the following basic element of regular expressions

We shall see how to use NFA transition graphs to recognize them.

Empty string & character #

Concatenation #

Where the dashed arrows mean that there could be multiple states and transitions within A and B respectively.

Alternative #

Repetition #

Example #

Translate the regular expression ab|a into an NFA according to Thompson's construction.

First, use the concatenation technique on ab

Then we form another copy of the machine for a and use the alternative technique get the complete NFA for ab|a

From an NFA to a DFA #

For each state , the closure set is a set of NFA states reachable from NFA state on -transitions alone.

Consider the following NFA corresponding to the regular expression a* under Thompson’s construction

In this NFA, we have

As we can see, the closure set for state must contains itself. Next, we shall find the transitions between these closure sets. We start from , and we examine what states we can go to from state 1, 2 and 4 but not using -transition. Here, there's only one transition, , therefore

And keep going with

By now, we've walk through all of the transitions and we get a DFA transition graph

Example 1 #

Let's look at a more complicated example

Perform the same procedures as above

Noted that if the new state contains a final state, then it becomes a final state as well.

Example 2 #

Consider the regular expression and the corresponding NFA transition graph

letter(letter|digit)*