Download project documentation

The Thompson’s Construction algorithm provides a way to construct the NFA of
some part from its subparts, such that the resulting NFA accepts the desired language.
However, the regular expression grammar we have employed has other features and
operations that are not explicitly described in the algorithm. Although these features
can be defined in terms of the basic features and operations covered in the algorithm,
the definition will be inefficient, as will be seen later as we describe the algorithm.
We begin by describing the basic features and operations covered in the algorithm. In
the following illustrations, the states drawn outside boxes are those that have been
newly added.
If we have a regular expression consisting of only one symbol s, then an NFA that
accepts the same language is given by:
Figure II-5: NFA for a One-Symbol RegEx
This shows how the function NfaFromSymbol is implemented.
Now, suppose that we have the regular expression r | s, where r and s represent any
two regular expressions. Suppose that we have successfully constructed the NFA of
the regular expression r and that of the regular expression s. We can construct an
NFA that accepts the same language of the regular expression r | s as follows:
Figure II-6: NFA for Two ORed RegEx's
This shows how the Or function used in the first semantic rule is implemented.
Assume that we are to construct the NFA equivalent to the regular expression r s, and
inductively assume that we have available the NFA of r and the NFA of s. Then, we
can construct the NFA of their concatenation by eliminating the start state of s after
duplicating all its transitions into the final state of r, and setting as the final state of
the new NFA the final state of s. The configuration is shown below: