lib/nfa.js
function(startState) {
        let dfa = new DFA();
        let stateMap = {};

        let epsilonNFASetCache = {}; // NFA-set -> NFA-set

        let startOrigin = {
            [startState]: 1
        };
        let start = this.epsilonClosure(startOrigin);
        epsilonNFASetCache[hashNFAStates(startOrigin)] = start;

        let dfaStates = {},
            newAdded = [];
        let last = 0,
            offset = 0; // distance between last state and current state
        dfaStates[hashNFAStates(start)] = 0; // default, the start state for DFA is 0
        stateMap[0] = start;
        newAdded.push(start);

        while (newAdded.length) {
            let newAddedTmp = [];

            for (let i = 0, n = newAdded.length; i < n; i++) {
                let stateSet = newAdded[i];
                let newMap = this._getNFASetTransitionMap(stateSet);

                let currentDFAState = i + offset;
                for (let letter in newMap) {
                    let toSet = newMap[letter];
                    let hashKey = hashNFAStates(toSet);
                    // find new state
                    let newItem = null;
                    if (epsilonNFASetCache[hashKey]) {
                        newItem = epsilonNFASetCache[hashKey];
                    } else {
                        newItem = this.epsilonClosure(newMap[letter]);
                    }
                    let newItemHashKey = hashNFAStates(newItem);
                    //
                    if (dfaStates[newItemHashKey] !== undefined) {
                        dfa.addTransition(currentDFAState, letter, dfaStates[newItemHashKey]);
                    } else {
                        // find new item
                        last++; // last + 1 as new DFA state
                        dfaStates[newItemHashKey] = last;
                        stateMap[last] = newItem;
                        newAddedTmp.push(newItem);

                        // build the connection from (index + offset) -> last
                        dfa.addTransition(currentDFAState, letter, last);
                    }
                }
            }

            offset += newAdded.length;
            newAdded = newAddedTmp;
        }

        return {
            dfa,
            stateMap
        };
    }
function(startState) {
        let dfa = new DFA();
        let stateMap = {};

        let epsilonNFASetCache = {}; // NFA-set -> NFA-set

        let startOrigin = {
            [startState]: 1
        };
        let start = this.epsilonClosure(startOrigin);
        epsilonNFASetCache[hashNFAStates(startOrigin)] = start;

        let dfaStates = {},
            newAdded = [];
        let last = 0,
            offset = 0; // distance between last state and current state
        dfaStates[hashNFAStates(start)] = 0; // default, the start state for DFA is 0
        stateMap[0] = start;
        newAdded.push(start);

        while (newAdded.length) {
            let newAddedTmp = [];

            for (let i = 0, n = newAdded.length; i < n; i++) {
                let stateSet = newAdded[i];
                let newMap = this._getNFASetTransitionMap(stateSet);

                let currentDFAState = i + offset;
                for (let letter in newMap) {
                    let toSet = newMap[letter];
                    let hashKey = hashNFAStates(toSet);
                    // find new state
                    let newItem = null;
                    if (epsilonNFASetCache[hashKey]) {
                        newItem = epsilonNFASetCache[hashKey];
                    } else {
                        newItem = this.epsilonClosure(newMap[letter]);
                    }
                    let newItemHashKey = hashNFAStates(newItem);
                    //
                    if (dfaStates[newItemHashKey] !== undefined) {
                        dfa.addTransition(currentDFAState, letter, dfaStates[newItemHashKey]);
                    } else {
                        // find new item
                        last++; // last + 1 as new DFA state
                        dfaStates[newItemHashKey] = last;
                        stateMap[last] = newItem;
                        newAddedTmp.push(newItem);

                        // build the connection from (index + offset) -> last
                        dfa.addTransition(currentDFAState, letter, last);
                    }
                }
            }

            offset += newAdded.length;
            newAdded = newAddedTmp;
        }

        return {
            dfa,
            stateMap
        };
    }
function ( startState ) { let dfa = new DFA ( ) ; let stateMap = { } ; let epsilonNFASetCache = { } ; // NFA-set -> NFA-set let startOrigin = { [ startState ] : 1 } ; let start = this . epsilonClosure ( startOrigin ) ; epsilonNFASetCache [ hashNFAStates ( startOrigin ) ] = start ; let dfaStates = { } , newAdded = [ ] ; let last = 0 , offset = 0 ; // distance between last state and current state dfaStates [ hashNFAStates ( start ) ] = 0 ; // default, the start state for DFA is 0 stateMap [ 0 ] = start ; newAdded . push ( start ) ; while ( newAdded . length ) { let newAddedTmp = [ ] ; for ( let i = 0 , n = newAdded . length ; i < n ; i ++ ) { let stateSet = newAdded [ i ] ; let newMap = this . _getNFASetTransitionMap ( stateSet ) ; let currentDFAState = i + offset ; for ( let letter in newMap ) { let toSet = newMap [ letter ] ; let hashKey = hashNFAStates ( toSet ) ; // find new state let newItem = null ; if ( epsilonNFASetCache [ hashKey ] ) { newItem = epsilonNFASetCache [ hashKey ] ; } else { newItem = this . epsilonClosure ( newMap [ letter ] ) ; } let newItemHashKey = hashNFAStates ( newItem ) ; // if ( dfaStates [ newItemHashKey ] !== undefined ) { dfa . addTransition ( currentDFAState , letter , dfaStates [ newItemHashKey ] ) ; } else { // find new item last ++ ; // last + 1 as new DFA state dfaStates [ newItemHashKey ] = last ; stateMap [ last ] = newItem ; newAddedTmp . push ( newItem ) ; // build the connection from (index + offset) -> last dfa . addTransition ( currentDFAState , letter , last ) ; } } } offset += newAdded . length ; newAdded = newAddedTmp ; } return { dfa , stateMap } ; }
generate a new DFA and record which nfa states composed to a new DFA state
generate a new DFA and record which nfa states composed to a new DFA state