Implementing DFA minmization algorithm with JAVA ArrayList -

Implementing DFA minmization algorithm with JAVA ArrayList -

i have implemented dfa minimization algorithm array lists, doesn't homecoming right answer. if point out part of algorithm missing, appreciate it.(and correction on whether have used efficient way implement it).

the programme supposed read info file , work on it. function has nil data. have hard coded work.

the method implements algorithm named (unreachablestates)

debug i: went thorough code, , found out problem loop surround look | temp.add(transitiontable[j][i]) |. work first 2 iterations, after not consider states. challenge prepare it.

package dregaut; import java.io.*; import java.util.arraylist; import java.util.iterator; public class dfamin { // global variables hold info file private int numstates,numalphabets,numfinalstates; private char alphabets[]; private boolean finalstates[]; private int [][] transitiontable; /** * @param args * @throws ioexception * @throws numberfor matexception */ public static void main(string[] args) throws numberfor matexception, ioexception { int numstates,numalphabets,numfinalstates; char alphabets[]; boolean finalstates[]; int [][] transitiontable; // take file name , open stream read fileinputstream filestream = new fileinputstream("/path/to/file/trace"); bufferedreader br = new bufferedreader(new inputstreamreader(filestream)); // store each line file string line; // read each line file while((line = br.readline()) != null){ // read single spaced info each line string [] splittedline = line.split(" "); // read numstates,numalphabets 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 line , read transition table (int row=0;row<numstates;row++){ (int col=0;col<numalphabets;col++){ transitiontable[row][col] = integer.parseint(splittedline[tt]); tt++; } // end of -loop go thorough alphabets } // end of -loop 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 boolean[numstates]; int start = 3+numstates*numalphabets ; int end = (3+(numstates*numalphabets))+numfinalstates; (int fs=start;fs<end;fs++){ finalstates[ integer.parseint(splittedline[fs])] = true; //system.out.println(finalstates[z]); z++; } // end of -loop read final states dfamin x = new dfamin(numstates,numalphabets,numfinalstates,finalstates,transitiontable); //x.minimizer(); //system.out.println(x); //system.out.println("======================"); int [][] ttt = {{1,2},{0,2},{1,0},{1,2}}; x.unreachablestates(4,2,ttt); } // end of while-loop read file // close stream br.close(); } dfamin(int ns,int na,int nfs,boolean fs[], int [][] tt){ numstates = ns; numalphabets = na; numfinalstates = nfs; //alphabets = a; finalstates = fs; transitiontable = tt; } // end of dfaminimizer constructor /* * method minmize dfa */ public void minimizer(){ } // end of minimizer method /* * method find unreachable states * */ public void unreachablestates(int numstates, int numalphabets, int [][] transitiontable){ // initialize list hold temporary list of states in arraylist<integer> reachablestates =new arraylist(); arraylist<integer> newstates = new arraylist(); // start state 0 reachablestates.add(0); newstates.add(0); // temporary array hold reachable states arraylist<integer> temp = new arraylist(); // loop until there info in newstates { // empty temp array temp.clear(); (int j=0;j<newstates.size();j++){ (int i=0; i<numalphabets;i++){ //system.out.printf("alphabets:%d state:%ds ",i,j); //system.out.printf("state:%d newstates:%d \n",j, newstates.get(j)); //system.out.printf("transitiontable: %d\n",transitiontable[j][i]); temp.add(transitiontable[j][i]); //system.out.printf("temp[%d] = %d",i,temp.get(i)); //system.out.printf("alphabets: %d", i); } // end of -loop go thorough characters //system.out.printf("newstates: %d\n",newstates.get(j)); } // end of -loop go thorough elements of newstates array list //system.out.printf("newstatesize: %d",newstates.size()); // clear newstates list newstates.clear(); //system.out.printf("temp size: %d", temp.size()); // add together elements in temp, not in reachablestates newstates (int z=0;z<temp.size();z++){ (int z1=0; z1<reachablestates.size();z1++){ // if state present, don't add together if (temp.get(z) == reachablestates.get(z1)){ break; } if (temp.get(z) != reachablestates.get(z1) && z1 == reachablestates.size()-1){ //system.out.printf("temp:%d reachablestates:%d z:%d z1:%d \n",temp.get(z),reachablestates.get(z1),z,z1); newstates.add(temp.get(z)); } //system.out.printf("reachablestates: %d ", reachablestates.get(z1)); } // end of -loop go thorough reachablestates elements , check if match } // end of -loop thorugh temp states //system.out.printf("newstates size after loop:%d \n",newstates.size()); if (!newstates.isempty()){ // add together newstates elements reachable states (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)); } } /* //system.out.println(); system.out.printf("reachable states:"); (int y=0;y<reachablestates.size();y++){ system.out.printf("%d",reachablestates.get(y)); } system.out.printf("end!\n"); */ } while(!newstates.isempty()); system.out.printf("reachable sadfstates: "); (int w = 0;w<reachablestates.size()-1;w++){ system.out.printf(" %d ",reachablestates.get(w)); } system.out.println(); } // end of unreachablestates method }

after hr of debugging, got working. had alter problem mentioned in debug (in question). changed following:

transitiontable[newstates.get(j)][i]

java algorithm arraylist dfa