Finite Automata

A finite automata algorithm is a step-by-step method used to check if a sequence of symbols (like letters or numbers) matches a specific pattern. It works by moving through a series of states based on the input, starting from an initial state and possibly ending in a state that signals a match.

/**
 * @file Finite Automata
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Generator function that matches a pattern using a finite automaton. It
 * reports every occurrence of the pattern by yielding the starting index of
 * each match.
 *
 * @param T The text in which to search for the pattern.
 * @param d The transition function that defines state transitions based on
 *   current state and the current character.
 * @param m The length of the pattern which corresponds to the acceptance state
 *   in the finite automaton.
 * @yields The starting index of each pattern occurrence in the text.
 */
function* finiteAutomatonMatcher(
  T: string,
  d: (q: number, a: string) => number,
  m: number,
): Generator<number> {
  const n = T.length;
  let q = 0;
  for (let i = 0; i < n; i++) {
    q = d(q, T[i]);
    if (q === m) {
      console.log(`Pattern occurs with shift ${i - m + 1}`);
      yield i - m + 1;
    }
  }
}

/**
 * Constructs a transition function for a given pattern and alphabet. The
 * function maps each state and input character to a new state.
 *
 * @param pattern The pattern for which the transition function is constructed.
 * @param alphabet The set of characters considered in the text and pattern.
 * @returns A function that takes a state and char and returns the next state.
 */
function computeTransitionFunction(
  pattern: string,
  alphabet: string,
): (q: number, a: string) => number {
  const m = pattern.length;
  const transitionTable: Record<number, Record<string, number>> = {};

for (let q = 0; q <= m; q++) {
    transitionTable[q] = {};
    for (const a of alphabet) {
      let k = Math.min(m, q + 1);
      while (k > 0) {
        const suffix = pattern.slice(0, q) + a;
        const candidate = pattern.slice(0, k);
        if (suffix.endsWith(candidate)) break;
        k -= 1;
      }

transitionTable[q][a] = k;
    }
  }

return (q: number, a: string) => transitionTable[q][a];
}

// Usage
(() => {
  // Compute Transition Function
  const pattern = 'ababaca';
  const alphabet = 'abc';
  const suffixFunction = computeTransitionFunction(pattern, alphabet);

const expected: Array<Record<string, number>> = [
    {a: 1, b: 0, c: 0},
    {a: 1, b: 2, c: 0},
    {a: 3, b: 0, c: 0},
    {a: 1, b: 4, c: 0},
    {a: 5, b: 0, c: 0},
    {a: 1, b: 4, c: 6},
    {a: 7, b: 0, c: 0},
    {a: 1, b: 2, c: 0},
  ];

for (const [i, element] of expected.entries()) {
    const actualA = suffixFunction(i, 'a');
    const expectedA = element.a;
    if (actualA !== expectedA) {
      throw new Error(`Expected ${expectedA} but got ${actualA}`);
    }

const actualB = suffixFunction(i, 'b');
    const expectedB = element.b;
    if (actualB !== expectedB) {
      throw new Error(`Expected ${expectedB} but got ${actualB}`);
    }

const actualC = suffixFunction(i, 'c');
    const expectedC = element.c;
    if (actualC !== expectedC) {
      throw new Error(`Expected ${expectedC} but got ${actualC}`);
    }
  }

// Finite Automaton Matcher
  const iterator = finiteAutomatonMatcher(
    pattern,
    suffixFunction,
    pattern.length,
  );
  const actualMatches = Array.from(iterator);
  const expectedMatchCount = 1;
  if (actualMatches.length !== expectedMatchCount) {
    throw new Error(
      `Expected ${expectedMatchCount} matches but got ${actualMatches.length}`,
    );
  }
})();