What is the deterministic finitite automaton (DFA) for the regex ".*b."

Question

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:

Answer 1

Every language described by a regular expression has a DFA – 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 $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.

Answer 2

Can this [the regular expression $.*b.$, my NFA] converted to a DFA?

yes and not sure about your NFA, it's not in standard form and looks too complicated for the regular expression you're trying to accomplish

Is there even a DFA for this regular expression?

yes, there is for every regular expression

Or am I missing something?

several things, first of all you didn't miss that the DFA you got isn't quite correct. For constructing an NFA one usually uses Thompson's construction and NFA minimization, that won't give you your version of an NFA, so you missed that. To get from an NFA to a DFA one usually uses $\epsilon$-move elimination, initial state reduction to one, powerset construction and finally DFA minimization, so you missed that as well.

The minimal NFA for the regular expression $.*b.$ reached by standard means would be:

$\mathcal N \mathcal A=(Q,\Sigma,\delta,s,F)$ with alphabet $\Sigma=\{b,\neg b\}$, set of states $Q=\{0,1,2\}$, initial state $s=0$, set of accepting states $F=\{2\}$ and transition function $\delta:Q\times\Sigma\to\mathcal P(Q)$ with the following defined transitions:

$\delta(0,b)=\{0,1\}$, $\delta(0,\neg b)=\{0\}$, $\delta(1,b)=\{2\}$ and $\delta(1,\neg b)=\{2\}$

From that a minimal DFA is obviously defined as follows:

$\mathcal A=(Q',\Sigma,\delta',q_0,F')$ with the same alphabet, set of states $Q'=\{0,1,2,3\}$, initial state $q_0=0$, set of accepting states $F=\{2,3\}$ and transition function $\delta':Q'\times\Sigma\to Q'$ with the following defined transitions:

$\delta'(0,b)=1$, $\delta'(0,\neg b)=0$, $\delta'(1,b)=2$, $\delta'(1,\neg b)=3$, $\delta'(2,b)=2$, $\delta'(2,\neg b)=3$, $\delta'(3,b)=1$ and $\delta'(3,\neg b)=0$

That's essentially the same DFA that you got from David, just get rid of those ugly $\epsilon$-moves at the end, give states proper names and instead of $'.'$-moves name them $\neg b$-moves