From a Regular Expression to an NFA

Thompson's construction is an NFA from a regular expression.

The Thompson's construction is guided by the syntax of the regular expression with cases following the cases in the definition of regular expression.

1. ε is a regular expression that denotes {ε}, the set containing just the empty string.
   diagram
   where i is a new start state and f is a new accepting state. This NFA recognizes {ε}.
2. If a is a symbol in the alphabet, a ∑, then regular expression 'a' denotes {a} and the set containing just 'a' symbol.
   diagram
   This NFA recognizes {a}.
3. Suppose, s and t are regular expressions denoting L{s} and L(t) respectively, then
   1. s/r is a regular expression denoting L(s) L(t)
   2. st is a regular expression denoting L(s) L(t)
      diagram
   3. s* is a regular expression denoting L(s)*
      diagram
   4. (s) is a regular expression denoting L(s) and can be used for putting parenthesis around regular expression

Example: Use above algorithm, Thompson's construction, to construct NFA for the regular expression r = (a|b)* abb.

First constant the parse tree for r = (a|b)* abb.

figure

• For r₁ - use case 2.

figure

• For r₂ - use case 2.

figure

• For r₃ - use case 3a

figure

• For r₅ - use case 3c

figure

We have r₅ = (a|b)*

• For r₆ - use case 2

figure

• and for r₇ - use case 3b

figure

We get r₇ =(a|b)* a

Similarly for r₈ and r₁₀ - use case 2

figure

figure

And get r₁₁ by case 3b

figure

We have r = (a|b)*abb.