0
我想实现Hopcroft的算法来最小化DFA WIKIPEDIA。到现在为止，我可以删除无法访问的状态。问题是我不明白这个算法。我不知道如何实现它。有人可以解释吗？或者可以扩展算法，使其更易于实现。我不明白的算法的以下部分都：Hopcroft的算法 - DFA最小化
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();
}
}
这是很难解释的算法，以直观的方式没有抽出DFA和行走通过它在白板上。在实现它的过程中，最好（根据我的经验）将伪代码作为注释，并编写代码来实现每个片段。对于这个特定的算法，使用一个实际的数学样式的Set类（支持union和intersect之类的东西）可以帮助你很大程度地处理这些问题，以便你可以逐字执行一些东西（注意这不一定是最有效的方法，但它让你更容易翻译伪码）。 – 2014-11-04 05:57:03