NAME:
LOGIN:
PRECEPTS:
COS 226 Exercises on Pattern Matching
References: Section 5.4 in Algorithms, 4th edition
1.
Draw an NFA for the regular expression
( ( A * | ( B C ) * D ) * ) using the construction described in
Section 5.4.
Distinguish the match transitions from the epsilon transitions in your drawing.
2.
Show, in the style of the figure on page 798
(by specifying the set of states after each step),
a sequence of
transitions that demonstrates that the NFA that you drew above
recognizes the text string
A A D B C D A D D.
You do not need to redraw the NFA after each step.