I'm looking for a finite state machine that can match inputs to the regular expression
.*b. deterministically (i.e. it cannot change state w/o being fed input and the transition to a new state is solely determined by the current state and the input word).
Consider the following examples that should be matched by the automaton:
abcabc. The first one reflects a "happy path" while the remaining all require some level of backtracking, because the automaton will incorrectly match the first
b it finds in the input with the
b in the pattern.
My nondeterministic attempt looks like this:
You can see from the conditions on the edges that the transition to a new state not only depends on the current state and the input word, but also on the previous input word.
Can this converted to a DFA? Is there even a DFA for this regular expression?
This site claims yes, but in my opinion the DFA it produces for the regex cannot match all the examples w/o doing some magic behind the curtains:
Consider the transition steps for the example
c: fail because there is no matching edge from state
Or am I missing something?
Based on David Richerby's answer I drew this DFA: