What is the deterministic finitite automaton (DFA) for the regex ".*b." 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: abc, abbc, abcbc, 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 abbc:


word a: 0-.-&gt;1
word b: 1-b-&gt;2
word b: 2-.-&gt;3
word c: fail because there is no matching edge from state 3


Or am I missing something?



Based on David Richerby's answer I drew this DFA:
Every language described by a regular expression has a DFA&nbsp;&ndash; this is Kleene's theorem (not to be confused with Kleene's recursion theorems, which are something completely different).  Standard algorithms to translate from regular expressions to automata give nondeterministic automata (NFAs), such as the one you found on the web.  There are standard algorithms to determinize NFAs but they make the state space exponentially larger.

In this case, though, it's straightforward to produce a DFA by thinking about the language you're interested in. The language is all strings whose second-to-last character is&nbsp;$b$. So your automaton needs to accept if it gets to the end of the string and the previous character it saw was a&nbsp;$b$.  I don't have any drawing software to hand but the following textual description is, I think, more useful.  You need four states, corresponding to the combinations of "the character I just read was/was not&nbsp;$b$" and "the character before that was/was not&nbsp;$b$". You start in (not&nbsp;$b$, not&nbsp;$b$), since you haven't read any&nbsp;$b$s before you've read any characters.  The transition function and so on should be pretty obvious.