If pattern P=ba◊b and assuming that ∑ = {a,b} then P matches baab and babb.Construct DFA(P) for P=ba◊b?

Question

The string matching automaton searches for an exact match of pattern P in text t T. We would like to introduce a new symbol into the pattern which means "match any single character." Let ◊ be this new symbol. If pattern P=ba◊b and assuming that ∑ = {a,b} then P matches baab and babb. (a) Construct DFA(P) for P=ba◊b. (b) Run it on the text string T = abbabaababbb.

Answer 1

Constructing an NFA for this is pretty trivial. First state loops back to itself on a,b. Go to the second state on b. Go to the third state on a. Go to the fourth state on a or b. Go to the fifth accepting state on b. From that you could construct a DFA.

To do a DFA from scratch, in the first state you'd just keep looping as long as you see a. Once you see a b, go to the second state.

In the second state (we got a b), if you get another b, go back to the first state. If you see an a, go to the third state.

In the third state (we got a b followed by an a), on a, go to a fourth state. On b, go to a fifth state.

In the fourth state (we got baa), if you get a b, you have a match, so go to the sixth accepting state. If you get an a, you have to start over, so go back to the first state.

In the fifth state (we got bab), if you get a b, you have a match, so go to the sixth accepting state. If you get an a (and this part is tricky), you STILL have ba. So instead of going back to the first state, go to the third.

In the sixth state, which is accepting, if you get an a or a b, you just go back to the same state (cuz you already found the substring).