Converting a regular expression to a NFA

Next: Kleene's Theorem Up: Non-Deterministic Finite-State Automata Previous: Non-Deterministic Finite-State Automata Contents

We will use the rules which defined a regular expression as a basis for the construction:

The NFA representing the empty string is:

$\begin{picture}(77.00,35.00) \put(10.00,10.00){\vector(1,0){3.00}} \put(20.00,10... ...ctor(3,-1){2}} \put(45.00,22.00){\makebox(0,0)[cc]{$\varepsilon$}} \end{picture}$
If the regular expression is just a character, eg. a, then the corresponding NFA is :

$\begin{picture}(77.00,35.00) \put(10.00,10.00){\vector(1,0){3.00}} \put(20.00,10... ...0,15.50){\vector(3,-1){2}} \put(45.00,22.00){\makebox(0,0)[cc]{a}} \end{picture}$
The union operator is represented by a choice of transitions from a node; thus a|b can be represented as:

$\begin{picture}(77.00,35.00) \put(10.00,20.00){\vector(1,0){3.00}} \put(20.00,20... ....00,14.50){\vector(3,1){2}} \put(45.00,8.00){\makebox(0,0)[cc]{b}} \end{picture}$
Concatenation simply involves connecting one NFA to the other; eg. ab is:

$\begin{picture}(77.00,35.00) \put(10.00,10.00){\vector(1,0){3.00}} \put(20.00,10... ...0,16.00){\vector(2,-1){2}} \put(65.00,22.00){\makebox(0,0)[cc]{b}} \end{picture}$
The Kleene closure must allow for taking zero or more instances of the letter from the input; thus a* looks like:

$\begin{picture}(77.00,55.00) \put(10.00,30.00){\vector(1,0){3.00}} \put(20.00,30... ...vector(2,1){2}} \put(65.00,8.00){\makebox(0,0)[cc]{$\varepsilon$}} \end{picture}$

James Power 2002-11-29