NAME:

LOGIN:

PRECEPT:

COLLABORATORS:

COS 226 Exercises on Pattern Matching


1. Give the DFA for for the string aaabbaaaabbb using the binary KMP construction by filling in the table below. 


  |   0    1    2    3    4    5    6    7    8    9   10   11   12
--------------------------------------------------------------------
a |   1    2
  |
b |   0    0

2. Draw an NFA for the regular expression (a | (bc)*d)* using the construction given in the lecture notes. Give the NFA after each step of the construction and circle your final answer. 


                (a | (bc)*d)*
Step 1:   0  ------------------->   1