$(25$ points$)$ Create the Knuth$-$Morris$-$Pratt DFA for the string aabaacab over the alphabet $\{a,b,c\}.$ As usual, state $0$ is the start state and state $8$ is the accept state.

$(25$ points$)$ Build the NFA for the pattern $(((B^{***}|)\}$ Then, check whether the NFA algorithm matches the input string BACABA.

Hint: show $-$transitions are shown with dashed lines, the match transitions in solid lines.