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

Just list the set of states after each step. The solution is started for illustration purposes. 

After ε-transitions from start: 0, 1, 2, 3 ...

After matching A: ...

After ε-trans: ...

After matching A: ...