java - Hopcroft 算法 - DFA 最小化

Question

我想实现 Hopcroft 的算法来最小化 DFA WIKIPEDIA .到目前为止，我可以删除无法访问的状态。问题是我不明白这个算法。我不知道如何实现它。有人可以解释一下吗？或者可以扩展算法，使其更易于实现。我根本没有得到算法的以下部分:

 let X be the set of states for which a transition on c leads to a state in A
      for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
           replace Y in P by the two sets X ∩ Y and Y \ X

算法如下:

到目前为止我实现了什么(写得不好，完成后会清理):

    package dRegAut;
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;


public class dfamin {

    // Global variables to hold data from the file
    private int numStates,numAlphabets,numFinalStates;
    private char alphabets[];
    private int finalStates[];
    private int [][] transitionTable;



    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {

        int numStates,numAlphabets,numFinalStates;
        char alphabets[];
        int finalStates[];
        int [][] transitionTable;

        /*
         * INPUT FILE FORMAT: numberOfStates numberofAlphabets transitions1 transtions2 ... numberOfFianlStates FinalState(s)
         * Example: 
         *          8 2 1 5 6 2 0 2 2 6 7 5 2 6 6 4 6 2 2 2 6
         *          5 2 0 1 0 1 3 4 3 4 2 4 3 0 2 3
         *          8 2 1 0 0 2 3 1 3 0 3 5 6 4 5 6 6 3 1 3
         *          9 2 1 4 2 5 3 7 4 7 5 8 6 1 7 1 8 2 0 4 3 2 5 8
         */

        // Take file name and open a stream to read it
        FileInputStream fileStream = new FileInputStream("/path/to/file");
        BufferedReader br = new BufferedReader(new InputStreamReader(fileStream));

        // Store each line from the file
        String line;

        // Read each line from file
        while((line = br.readLine()) != null){

            // Read single spaced data from each line
            String [] splittedLine = line.split(" ");

            // Read numStates,numAlphabets from the line
            numStates = Integer.parseInt(splittedLine[0]);
            numAlphabets = Integer.parseInt(splittedLine[1]);
            //for(int a=0;a<numAlphabets;a++){
                //alphabets[a] = '0';
            //}
            transitionTable = new int[numStates][numAlphabets];
            int tt= 2;
            // Loop thorough the line and read transition table
            for(int row=0;row<numStates;row++){

                for(int col=0;col<numAlphabets;col++){
                    transitionTable[row][col] = Integer.parseInt(splittedLine[tt]);

                    tt++;

                }// End of for-loop to go thorough alphabets
            }// End of for-loop to go thorough states

            // Read number of final states
            numFinalStates = Integer.parseInt(splittedLine[2+numStates*numAlphabets]);
            //System.out.println(numFinalStates);
            // Read final states
            int z=0;
            finalStates = new int[numFinalStates];
            int start = 3+numStates*numAlphabets ;
            int end = (3+(numStates*numAlphabets))+numFinalStates;
            for(int fs=start;fs<end;fs++){
                finalStates[z] = Integer.parseInt(splittedLine[fs]);
                //System.out.println(finalStates[z]);
                z++;
            }// End of for-loop to read all final states
            dfamin x = new dfamin(numStates,numAlphabets,numFinalStates,finalStates,transitionTable);
            x.minimizer();
            System.out.println(x);



        }// End of while-loop to read file

        // Close the stream
        br.close();

    }

    dfamin(int nS,int nA,int nFS,int fS[], int [][] tT){
        numStates = nS;
        numAlphabets = nA;
        numFinalStates = nFS;
        //alphabets = a;
        finalStates = fS;
        transitionTable = tT;

    }// End of DFAMinimizer constructor

    /*
     * A method to minmize the dfa  
     */

    public void minimizer(){

        // Remove unreachable States
        ArrayList<Integer> reachableStates = reachableStates(numStates, numAlphabets,transitionTable);

        // Store all final states
        ArrayList<Integer> fStates = new ArrayList<Integer>();
        // Loop thorugh finalStates array and transfer its data to array list
        for(int fs:finalStates){
            fStates.add(fs);
        }// End of for-loop

        // Store all non final states
        ArrayList<Integer> nonFStates = new ArrayList<Integer>();

        // Store only non final states in nonFstates
        nonFStates = nonFinalStates(reachableStates,fStates);

        //TODO: IMPLEMENT HOPCROFT's ALGORITHM


    }// End of minimizer method

    /*
     * unreachableStates - A method to find unreachable states of a DFA 
     * 
     */
    public ArrayList<Integer> reachableStates(int numStates, int numAlphabets, int [][] transitionTable){

        // Initialize a list to hold temporary list of states in it
        ArrayList<Integer> reachableStates =new ArrayList();
        ArrayList<Integer> newStates = new ArrayList();


        // Start from the state zero
        reachableStates.add(0);
        newStates.add(0);
        // Temporary array to hold reachable states
        ArrayList<Integer> temp = new ArrayList();
        // Loop until there is data in newStates
        do{
            // Empty temp array
            temp.clear();
            // Loop thorough all the states, and check for {p such that p=δ(q,c)};
            for(int j=0;j<newStates.size();j++){

                for(int i=0; i<numAlphabets;i++){
                    // If found add it to the temp set
                    temp.add(transitionTable[newStates.get(j)][i]);

                } // End of for-loop to go thorough all characters

            }// End of for-loop to go thorough all elements of the newStates array list

            // Clear newStates list
            newStates.clear();

            // Add the elements that are in temp, but are not in reachableStates to newStates
            // new_states := temp \ reachable_states;
            for(int z=0;z<temp.size();z++){

                for(int z1=0; z1<reachableStates.size();z1++){


                    // If the state was already present, don't add
                    if(temp.get(z) == reachableStates.get(z1)){
                        break;
                    }
                    if(temp.get(z) != reachableStates.get(z1) && z1 == reachableStates.size()-1){
                        // Only from temp to newstates if its not in reachablestates currently
                        newStates.add(temp.get(z));

                    }


                }// End of for-loop to go thorough all reachableStates elements and check if a match
            }// End of for-loop thorugh all temp states

            // If newStates list is not empty then add it to the reachableStates
            if(!newStates.isEmpty()){
                // Add the newStates elements to reachable states
                for(int y=0;y<newStates.size();y++){
                    //System.out.printf("newStates:%d newStatesSize:%d in %d",newStates.get(y),newStates.size(),y);
                    reachableStates.add(newStates.get(y));
                }
            }

        }while(!newStates.isEmpty());

        reachableStates = removeDuplicate(reachableStates);

        return reachableStates;

    }// End of unreachableStates method

    /*
     * removeDuplicate - a function to remove duplicate entries from an ArrayList
     * 
     */
    ArrayList<Integer> removeDuplicate(ArrayList<Integer> input){

        // Remove duplicate entries from reachableStates list
        // Compare the first index, with all other indexes, compare the second with all other indexes
        for(int i=0;i<input.size()-1;i++){

            for(int j=i+1;j<input.size();j++){
                // If dupblicate states remove it
                if(input.get(i) == input.get(j)){
                    input.remove(j);
                }
            }
        }// End of for-loop to remove duplicate entries from reachableList

        // Sort the list before returning
        Collections.sort(input);
        // Return the list
        return input;
    }// End of removeDuplicate method


    /*
     * nonFinalStates - a method to return an array list of nonfinal states, given all and final states
     * 
     */
    ArrayList<Integer> nonFinalStates(ArrayList<Integer> allStates, ArrayList<Integer> finalStates){
        // All non final States
        ArrayList<Integer> nonFinalStates = new ArrayList<Integer>();
        // Loop thorough allStates, and compare each state with the list of finalstates
        for(int i=0; i<allStates.size();i++){
            // Loop thorough list of final states
            for(int j=0; j<finalStates.size();j++){
                // If a state is final state
                if(allStates.get(i) == finalStates.get(j)){
                    // Then remove it from the list
                    allStates.remove(i);
                }
            }// End of for-loop to travers finalstates
        }// End of for-loop to traverse allstates

        return nonFinalStates;

    }



    // returns a string that is compatible with our input file specification
    public String toString()    {
        StringBuffer buf = new StringBuffer();
        //buf.append(" "+ numStates +" ");
        //buf.append ( numAlphabets + " " );
        buf.append("Transition Table: ");
        for ( int i = 0; i < numStates; i++ )   {
            for ( int j = 0; j < numAlphabets; j++ )    {
                buf.append ( " "+ transitionTable[i][j] + " " );
            }
        }

        buf.append ( "Number of Final State(s): "+numFinalStates + " Final State(s): " );
        for ( int i = 0; i < numFinalStates; i++ )

                buf.append ( finalStates[i] + " " );
        return buf.toString();
    }

}

Answer 1

如果无法仅通过接受/拒绝行为来判断 DFA 处于哪个状态，则将两个 DFA 状态称为等效。对于每种语言，接受该语言的最小 DFA 没有等效状态。

Hopcroft 的 DFA 最小化算法通过计算未最小化 DFA 的状态的等价类来工作。这种计算的核心是迭代，在每一步中，我们都有一个比等价更粗糙的状态分区(即，等价状态总是属于同一组分区)。

1. 初始分区是接受状态和拒绝状态。显然，这些并不等同。

2. 假设我们在当前分区的同一集合中有状态 q1 和 q2。设转移函数为 delta，如果存在符号 sigma 使得 delta(q1, sigma) 和 delta(q2, sigma) 在划分的不同集合中，那么我们通过粗糙度不变量知道这些状态不等价，即，存在一个字符串 x 使得 delta(delta(q1, sigma), x) 和 delta(delta(q2, sigma), x) 在接受/拒绝方面不同。但是 delta(delta(q1, sigma), x) = delta(q1, sigma x)，所以字符串 sigma x 区分了 q1 和 q2。您引用的逻辑是适本地拆分其中一个分区集。

3. 正确性证明的有趣部分是，当第 2 步不可能时，我们已经到达了真正的等价类。

伪代码看起来比这更复杂，因为它与我们找到步骤 2 的应用程序的效率有关。