Teeny-Weeny Iterable Finite State Machine

machine.js

/**
 * @template StateKey - Any value used to index a Map of Q
 * @template Transition - Any value used to index a Map of Transitions and an undefined value is an epsilon acceptor. Non-epsilon transitions are attempted first
 * @param {Map<StateKey & any, Map<Transition | undefined, ((transition?: any & StateKey) => StateKey)>>} Q - Where q0 is first q in Q, and final states are q in Q with empty transitions
 * @returns {Iterable<StateKey>} - Iterable machine where `machine.next(transition)` steps machine and returns next q.
 */
export function dfaFactory(Q) {
  /** @type {StateKey} */
  const q0 = Q.keys().next().value;
  let q = q0;
  /** @type {StateKey[]} */
  const fin = [];
  for (let [qN, transitions] of Q) if (transitions.size === 0) fin.push(qN);
  let done = fin.includes(q0);
  const machine = {
    /** @param {Transition} [transition] */
    next(transition) {
      if (!done) {
        q = Q.get(q)?.get(transition)?.() ?? q0; // no match! Reset
        done = fin.includes(q);
      }
      return { done, value: q };
    },
    get q() {
      return q;
    },
    [Symbol.iterator]() {
      return this;
    },
  };
  return machine;
}

xample.js

const states = new Map()
  .set("foo", new Map().set("fee", () => "bar"))
  .set("bar", new Map().set("fie", () => "baz"))
  .set("baz", new Map());

const machine = machineFactory(states);
console.log('q0:', machine.q);
console.log(`(q: ${machine.q}, Σ: ${'fee'}) => ${machine.next("fee").value}`);
console.log(`(q: ${machine.q}, Σ: ${'fie'}) => ${machine.next("fie").value}`);

/**
 * Output:
 * > q0: foo
 * > (q: foo, Σ: fee) => bar
 * > (q: bar, Σ: fie) => baz
 */