# 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-.->1
• word b: 1-b->2
• word b: 2-.->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:

• Can you give an example of a string that you think the DFA (from the site) won't match? – klaus Nov 3 '17 at 17:20
• @klaus I updated the question w/ an example. – Good Night Nerd Pride Nov 3 '17 at 17:30
• "Is there even a DFA for this regular expression?" there are DFAs for all regular expressions: this is Kleene's theorem (not to be confused with Kleene's recursion theorems, which are something completely different.) – David Richerby Nov 3 '17 at 17:40
• @DavidRicherby well that's good to now, but which one is it? – Good Night Nerd Pride Nov 3 '17 at 17:43

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 $b$. So your automaton needs to accept if it gets to the end of the string and the previous character it saw was a $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 $b$" and "the character before that was/was not $b$". You start in (not $b$, not $b$), since you haven't read any $b$s before you've read any characters. The transition function and so on should be pretty obvious.