/** 
     * Unordered pair of states. Used in minimization operation. 
     */
    static class UnorderedStatePair {
        
        State s1, s2;
        
        /** 
         * Constructs a new unordered pair. 
         */
        UnorderedStatePair(State s1, State s2) {
            this.s1 = s1;
            this.s2 = s2;
        }
        
        /** 
         * Checks whether two unordered pairs are equal. 
         */
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof UnorderedStatePair))
                return false;
            UnorderedStatePair ss = (UnorderedStatePair) obj;
            return (s1==ss.s1 && s2==ss.s2) || (s1==ss.s2 && s2==ss.s1);
        }
        
        /** 
         * Computes hash code for this object. 
         */
        @Override
        public int hashCode() {
            return s1.hashCode() + s2.hashCode();
        }
    }

    /** 
     * Constructs a new minimal automaton with the same language as this automaton. [Martin, Sec. 2.6] 
     * The input automaton is unmodified.
     * Note: this textbook algorithm is simple to understand but not very efficient 
     * compared to other existing algorithms.
     */
    public FA minimize() { 
        FA f = removeUnreachableStates();
        Set<UnorderedStatePair> marks = new HashSet<UnorderedStatePair>();
        List<State> statelist = new ArrayList<State>(f.states); // ensure consistent state order
        // first pass, divide into accept/reject states
        for (State p : statelist)
            for (State q : statelist) {
                if (p == q)
                    break; // traversing all *unordered* pairs of states
                if (f.accept.contains(p)!=f.accept.contains(q))
                    marks.add(new UnorderedStatePair(p, q));
            }
        // iteratively perform marking passes until nothing more happens
        boolean done = false;
        while (!done) { // (this could be made more efficient with a worklist)
            done = true;
            for (State p : statelist)
                for (State q : statelist) {
                    if (p == q)
                        break;
                    if (!marks.contains(new UnorderedStatePair(p, q))) 
                        for (char a : f.alphabet.symbols) {
                            State r = f.delta(p, a);
                            State s = f.delta(q, a);
                            if (marks.contains(new UnorderedStatePair(r, s))) {
                                marks.add(new UnorderedStatePair(p, q));
                                done = false;
                                break;
                            }
                        }
                }
        }
        // start building the new automaton
        FA n = new FA();
        n.alphabet = alphabet;
        Map<State,State> old2new = new HashMap<State,State>(); // map from old states to new states
        Map<State,State> new2old = new HashMap<State,State>(); // map from new states to representatives in old states
        // make new states
        for (State r : statelist) {
            boolean repr = true; // true if r is representative for its equivalence class
            for (State s : statelist) {
                if (r == s)
                    break;
                if (!marks.contains(new UnorderedStatePair(r, s))) {
                    old2new.put(r, old2new.get(s));
                    repr = false;
                    break;
                }
            }
            if (repr) {
                State p = new State();
                n.states.add(p);
                if (f.accept.contains(r))
                    n.accept.add(p);
                old2new.put(r, p);
                new2old.put(p, r);
            }
            if (r==f.initial)
                n.initial = old2new.get(r);
        }
        // make new transitions
        for (State p : n.states) {
            State r = new2old.get(p);
            for (char a : n.alphabet.symbols)
                n.transitions.put(new StateSymbolPair(p, a), old2new.get(f.delta(r, a)));
        }
        return n;
    }