NAME:
LOGIN:
PRECEPT:
COLLABORATORS:
COS 226 Exercises on Pattern Matching
1.
Draw the DFA for for the string
aaabbaaaabbb using the binary KMP construction.
Don't forget to label the start and accept state.
2.
Draw an NFA for the regular expression
(a | (bc)*d)* using the construction given in the
lecture notes.