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:

enter image description here

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:

enter image description here

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:

enter image description here

  • $\begingroup$ Can you give an example of a string that you think the DFA (from the site) won't match? $\endgroup$
    – klaus
    Nov 3 '17 at 17:20
  • $\begingroup$ @klaus I updated the question w/ an example. $\endgroup$ Nov 3 '17 at 17:30
  • $\begingroup$ "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.) $\endgroup$ Nov 3 '17 at 17:40
  • $\begingroup$ @DavidRicherby well that's good to now, but which one is it? $\endgroup$ Nov 3 '17 at 17:43

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.

  • $\begingroup$ Very insightful, thanks! I updated my question with a picture of the DFA you proposed. $\endgroup$ Nov 3 '17 at 18:40

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

  • $\begingroup$ So you decided that your first move on StackExchange is to dig up a more than 2 year old question that already had an accepted answer, only to practice your condescending tone? Way to go, cevra. Way to go. $\endgroup$ Jun 7 '20 at 10:40
  • $\begingroup$ why would it be relevant that the question is 2 years old and that there was already an accepted answer? your DFA you drew according to David's answer is not a DFA, it features ambiguous moves, moves without input and is incomplete (a DFA defines transitions for each state and each input). $\endgroup$
    – cevra
    Jun 7 '20 at 16:07
  • $\begingroup$ xkcd.com/386 $\endgroup$ Jun 7 '20 at 16:18
  • $\begingroup$ you shouldn't ask if you don't want a correct answer $\endgroup$
    – cevra
    Jun 8 '20 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.