*Checking a string ending with a DFA

What the DFA remembers

DFA stands for deterministic finite automaton. It has a finite set of states, and the current state plus the next input determines exactly one next state. Each cell in the table describes that decision.

This example accepts only 0 and 1. S0 means either nothing has been read or the last character was one. S1 remembers a trailing zero. S2 remembers a trailing 01. We don't need to store the entire input.

That's why another 1 takes S2 back to S0: 011 no longer ends in 01. A zero takes it to S1, because that zero could begin the next match.

To check whether a string ends in 01, we can look at its last two characters. We can also describe it with a state machine. In this example, I'm looking at what we need to remember as we read.

Three states are enough: no partial match, the last character was 0, and the last two characters were 01. Call them S0, S1 and S2.

We start in S0. For 001, the first zero takes us to S1, the second keeps us there, and the final one takes us to S2. If we're in S2 when the input ends, the string ends in 01.

Searching inside a string

This checks the ending. If we want to know whether 01 appeared anywhere, we can stop as soon as we reach the accepting state. For longer patterns, we need to work out which part of a match to remember after a mismatch.

For example, when searching for abc in aabc, the second a can start a new match. Consuming it and resetting straight to zero would miss that match. Those transitions are what I'd pay attention to when building a pattern matcher.

The JavaScript version

I can put the transition table directly into code and look up the next state for each character:

function endsWith01(input) {
  const transitions = {
    S0: { '0': 'S1', '1': 'S0' },
    S1: { '0': 'S1', '1': 'S2' },
    S2: { '0': 'S1', '1': 'S0' },
  };
  let state = 'S0';

  for (const char of input) {
    if (char !== '0' && char !== '1') {
      throw new Error('Input must contain only 0 and 1');
    }
    state = transitions[state][char];
  }

  return state === 'S2';
}

console.log(endsWith01('001')); // true
console.log(endsWith01('011')); // false
console.log(endsWith01(''));    // false

For a check this small in an application, I'd use input.endsWith('01'). The table is useful for understanding the mechanism. When modelling a protocol or a sequence of steps, I can ask the same questions: which state are we in, and where should this input take us?