- Construct an NFA for the given regular expression using Thomson’s algorithm.
Objective: learner will be able to design and implement a RE to NFA converter
Prerequisite: learner should be able to draw NFA manually for the given Regular Expression using Thompsons algorithm
Pre-lab exercise: String and File Handling in C or Java.
Procedure - Thompson’s Algorithm:
Use the regular expression definition rules as a basis for the construction:
1. Case epsilon : The NFA representing the empty string is:
0 epsilon 1
2. Case a : If the regular expression is just a single character ‘a’, then
the corresponding NFA is :
0 a 1
3. Case a|b : The union operator is represented by a choice of transitions
from a node
0 a 1 0 b 1
4. Case ab : Concatenation simply involves connecting one NFA to the other
0 a 1 1 b 2
5. Case a* : The Kleene closure must allow for taking zero or more instances of the
letter
0 epsilon 1 1 a 2 2 epsilon 3
0 epsilon 3 2 epsilon 1