## 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 r1 - use case 2.

figure

• For r2 - use case 2.

figure

• For r3 - use case 3a

figure

• For r5 - use case 3c

figure

We have r5 = (a|b)*

• For r6 - use case 2

figure

• and for r7 - use case 3b

figure

We get r7 =(a|b)* a

Similarly for r8 and r10 - use case 2

figure

figure

And get r11 by case 3b

figure

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