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;
    }
  });

  
  

  
  const all = [
    
    [nonAccepting, accepting]
      .filter(set => set.size > 0),
  ];


  let current;
  let previous;

  
  current = all[all.length - 1];

  
  previous = all[all.length - 2];

  
  while (!sameRow(current, previous)) {
    const newTransitionMap = {};

    for (const set of current) {
      
      const handledStates = {};

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

      
      
      restSets: for (const state of rest) {
        for (const handledState of Object.keys(handledStates)) {
          
          
          if (areEquivalent(state, handledState, table, alphabet)) {
            handledStates[handledState].add(state);
            handledStates[state] = handledStates[handledState];
            continue restSets;
          }
        }
        
        
        handledStates[state] = new Set([state]);
      }

      
      Object.assign(newTransitionMap, handledStates);
    }

    
    currentTransitionMap = newTransitionMap;

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

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

    
    current = all[all.length - 1];

    
    previous = all[all.length - 2];
  }

  
  

  
  const remaped = new Map();
  let idx = 1;
  current.forEach(set => remaped.set(set, idx++));

  
  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);

      
      let originalTransition;
      for (const originalState of set) {
        originalTransition = table[originalState][symbol];
        if (originalTransition) {
          break;
        }
      }

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

  
  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).
Takes a DFA and returns a minimized version of it compressing some states to groups ( using standard 0 - 1 - 2 - ... N - equivalence algorithm ) .