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 692, 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.