src/interpreter/finite-automaton/dfa/dfa-minimizer.js
function minimize(dfa) {
  const table = dfa.getTransitionTable();
  const allStates = Object.keys(table);
  const alphabet = dfa.getAlphabet();
  const accepting = dfa.getAcceptingStateNumbers();

  currentTransitionMap = {};

  const nonAccepting = new Set();

  allStates.forEach(state => {
    state = Number(state);
    const isAccepting = accepting.has(state);

    if (isAccepting) {
      currentTransitionMap[state] = accepting;
    } else {
      nonAccepting.add(state);
      currentTransitionMap[state] = nonAccepting;
    }
  });

  // ---------------------------------------------------------------------------
  // Step 1: build equivalent sets.

  // All [1..N] equivalent sets.
  const all = [
    // 0-equivalent sets.
    [nonAccepting, accepting]
      .filter(set => set.size > 0),
  ];


  let current;
  let previous;

  // Top of the stack is the current list of sets to analyze.
  current = all[all.length - 1];

  // Previous set (to check whether we need to stop).
  previous = all[all.length - 2];

  // Until we'll not have the same N and N-1 equivalent rows.
  while (!sameRow(current, previous)) {
    const newTransitionMap = {};

    for (const set of current) {
      // Handled states for this set.
      const handledStates = {};

      const [first, ...rest] = set;
      handledStates[first] = new Set([first]);

      // Have to compare each from the rest states with
      // the already handled states, and see if they are equivalent.
      restSets: for (const state of rest) {
        for (const handledState of Object.keys(handledStates)) {
          // This and some previously handled state are equivalent --
          // just append this state to the same set.
          if (areEquivalent(state, handledState, table, alphabet)) {
            handledStates[handledState].add(state);
            handledStates[state] = handledStates[handledState];
            continue restSets;
          }
        }
        // Else, this state is not equivalent to any of the
        // handled states -- allocate a new set for it.
        handledStates[state] = new Set([state]);
      }

      // Add these handled states to all states map.
      Object.assign(newTransitionMap, handledStates);
    }

    // Update current transition map for the handled row.
    currentTransitionMap = newTransitionMap;

    let newSets = new Set(
      Object.keys(newTransitionMap)
        .map(state => newTransitionMap[state])
    );

    all.push([...newSets]);

    // Top of the stack is the current.
    current = all[all.length - 1];

    // Previous set.
    previous = all[all.length - 2];
  }

  // ---------------------------------------------------------------------------
  // Step 2: build minimized table from the equivalent sets.

  // Remap state numbers from sets to index-based.
  const remaped = new Map();
  let idx = 1;
  current.forEach(set => remaped.set(set, idx++));

  // Build the minimized table from the calculated equivalent sets.
  const minimizedTable = {};

  const minimizedAcceptingStates = new Set();

  const updateAcceptingStates = (set, idx) => {
    for (const state of set) {
      if (accepting.has(state)) {
        minimizedAcceptingStates.add(idx);
      }
    }
  };

  for (const [set, idx] of remaped.entries()) {
    minimizedTable[idx] = {};
    for (const symbol of alphabet) {
      updateAcceptingStates(set, idx);

      // Determine original transition for this symbol from the set.
      let originalTransition;
      for (const originalState of set) {
        originalTransition = table[originalState][symbol];
        if (originalTransition) {
          break;
        }
      }

      if (originalTransition) {
        minimizedTable[idx][symbol] = remaped.get(
          currentTransitionMap[originalTransition]
        );
      }
    }
  }

  // Update the table, and accepting states on the original DFA.
  dfa.setTransitionTable(minimizedTable);
  dfa.setAcceptingStateNumbers(minimizedAcceptingStates);

  return dfa;
}
function minimize(dfa) {
  const table = dfa.getTransitionTable();
  const allStates = Object.keys(table);
  const alphabet = dfa.getAlphabet();
  const accepting = dfa.getAcceptingStateNumbers();

  currentTransitionMap = {};

  const nonAccepting = new Set();

  allStates.forEach(state => {
    state = Number(state);
    const isAccepting = accepting.has(state);

    if (isAccepting) {
      currentTransitionMap[state] = accepting;
    } else {
      nonAccepting.add(state);
      currentTransitionMap[state] = nonAccepting;
    }
  });

  // ---------------------------------------------------------------------------
  // Step 1: build equivalent sets.

  // All [1..N] equivalent sets.
  const all = [
    // 0-equivalent sets.
    [nonAccepting, accepting]
      .filter(set => set.size > 0),
  ];


  let current;
  let previous;

  // Top of the stack is the current list of sets to analyze.
  current = all[all.length - 1];

  // Previous set (to check whether we need to stop).
  previous = all[all.length - 2];

  // Until we'll not have the same N and N-1 equivalent rows.
  while (!sameRow(current, previous)) {
    const newTransitionMap = {};

    for (const set of current) {
      // Handled states for this set.
      const handledStates = {};

      const [first, ...rest] = set;
      handledStates[first] = new Set([first]);

      // Have to compare each from the rest states with
      // the already handled states, and see if they are equivalent.
      restSets: for (const state of rest) {
        for (const handledState of Object.keys(handledStates)) {
          // This and some previously handled state are equivalent --
          // just append this state to the same set.
          if (areEquivalent(state, handledState, table, alphabet)) {
            handledStates[handledState].add(state);
            handledStates[state] = handledStates[handledState];
            continue restSets;
          }
        }
        // Else, this state is not equivalent to any of the
        // handled states -- allocate a new set for it.
        handledStates[state] = new Set([state]);
      }

      // Add these handled states to all states map.
      Object.assign(newTransitionMap, handledStates);
    }

    // Update current transition map for the handled row.
    currentTransitionMap = newTransitionMap;

    let newSets = new Set(
      Object.keys(newTransitionMap)
        .map(state => newTransitionMap[state])
    );

    all.push([...newSets]);

    // Top of the stack is the current.
    current = all[all.length - 1];

    // Previous set.
    previous = all[all.length - 2];
  }

  // ---------------------------------------------------------------------------
  // Step 2: build minimized table from the equivalent sets.

  // Remap state numbers from sets to index-based.
  const remaped = new Map();
  let idx = 1;
  current.forEach(set => remaped.set(set, idx++));

  // Build the minimized table from the calculated equivalent sets.
  const minimizedTable = {};

  const minimizedAcceptingStates = new Set();

  const updateAcceptingStates = (set, idx) => {
    for (const state of set) {
      if (accepting.has(state)) {
        minimizedAcceptingStates.add(idx);
      }
    }
  };

  for (const [set, idx] of remaped.entries()) {
    minimizedTable[idx] = {};
    for (const symbol of alphabet) {
      updateAcceptingStates(set, idx);

      // Determine original transition for this symbol from the set.
      let originalTransition;
      for (const originalState of set) {
        originalTransition = table[originalState][symbol];
        if (originalTransition) {
          break;
        }
      }

      if (originalTransition) {
        minimizedTable[idx][symbol] = remaped.get(
          currentTransitionMap[originalTransition]
        );
      }
    }
  }

  // Update the table, and accepting states on the original DFA.
  dfa.setTransitionTable(minimizedTable);
  dfa.setAcceptingStateNumbers(minimizedAcceptingStates);

  return dfa;
}
Takes a DFA, and returns a minimized version of it
compressing some states to groups (using standard, 0-, 1-,
2-, ... N-equivalence algorithm).