0
Dop 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 등의 지원이 포함 된)를 사용하여 물건을 그대로 구현할 수 있습니다. (반드시 가장 효율적인 방법은 아니지만 반드시 의사 코드를 훨씬 쉽게 번역 할 수 있습니다). –