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 on pages 613-616. Distinguish the match transitions from the epsilon transitions.

2. Show, in the style of the figure on page 611, 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.