0
$\begingroup$

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

$\endgroup$
  • $\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$ – Good Night Nerd Pride 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$ – David Richerby Nov 3 '17 at 17:40
  • $\begingroup$ @DavidRicherby well that's good to now, but which one is it? $\endgroup$ – Good Night Nerd Pride Nov 3 '17 at 17:43
2
$\begingroup$

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.

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

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.