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.