2014-11-03 55 views
0

我已經用數組列表實現了DFA minimization algorithm,但是它沒有返回正確的答案。如果有人能指出我失蹤的算法的哪一部分,我將不勝感激(並糾正我是否使用了一種有效的方法來實現它)。用JAVA ArrayList實現DFA最小化算法

該程序應該從文件讀取數據,然後對其進行處理。但是這個功能與這些數據無關。我已經硬編碼它的工作。

實現該算法的方法被命名爲(unreachableStates)

DEBUG我:所以我就徹底的代碼,並發現問題是環繞式循環| temp.add(transitionTable [j] [i])|。這將適用於前2次迭代,但在此之後它將不考慮所有狀態。現在的挑戰是解決它。

enter image description here

package dRegAut; 

import java.io.*; 
import java.util.ArrayList; 
import java.util.Iterator; 

public class dfamin { 
    // Global variables to hold data from the 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 and open a stream to read it 
     FileInputStream fileStream = new FileInputStream("/path/to/file/trace"); 
     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 boolean[numStates]; 
      int start = 3+numStates*numAlphabets ; 
      int end = (3+(numStates*numAlphabets))+numFinalStates; 

      for (int fs=start;fs<end;fs++){ 
       finalStates[ Integer.parseInt(splittedLine[fs])] = true; 
       //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); 
      //System.out.println("======================"); 
      int [][] ttt = {{1,2},{0,2},{1,0},{1,2}}; 
      x.unreachableStates(4,2,ttt); 
     } // End of while-loop to read file 

     // Close the 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 

    /* 
    * A method to minmize the dfa 
    */ 
    public void minimizer(){ 

    } // End of minimizer method 

    /* 
    * A method to find unreachable states 
    * 
    */ 
    public void unreachableStates(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(); 
      for (int j=0;j<newStates.size();j++){ 
       for (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 for -loop to go thorough all characters 

       //System.out.printf("newStates: %d\n",newStates.get(j)); 
      } // End of for -loop to go thorough all elements of the newStates array list 


      //System.out.printf("newStateSize: %d",newStates.size()); 
      // Clear newStates list 
      newStates.clear(); 

      //System.out.printf("Temp Size: %d", temp.size()); 

      // Add the elements that are in temp, but are not in reachableStates to newStates 
      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){ 
         //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 for -loop to go thorough all reachableStates elements and check if a match 
      } // End of for -loop thorugh all temp states 
      //System.out.printf("NewStates Size after loop:%d \n",newStates.size()); 

      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)); 
       } 
      } 
      /* 
      //System.out.println(); 
      System.out.printf("reachable states:"); 
      for (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: "); 
     for (int w = 0;w<reachableStates.size()-1;w++){ 
      System.out.printf(" %d ",reachableStates.get(w)); 
     } 
     System.out.println(); 
    } // End of unreachableStates method 
} 
+0

這是太多的代碼與殘留太多殘留是有用的作爲一個問題。清理它,還要注意你首先要負責找出問題的出處:確保所有算法步驟都是單獨的方法,並測試它們以確定它們是否應該自己做。那樣有用嗎?測試他們看他們按順序運行時的行爲等等。然後,如果你仍然無法弄清楚,那麼這個地方可以提出這個問題,所有關於你已經嘗試過的東西的信息並沒有幫助你修理東西。 – 2014-11-03 23:43:18

+0

@ Mike'Pomax'Kamermans我實際上試圖調試它,(這就是爲什麼代碼中有這麼多評論),但無法弄清楚。但是我會再做一次, – aaa 2014-11-03 23:44:49

+0

重點關注沒有剩下的代碼,首先。通過一些硬編碼輸入使得'unreachableStates'方法可以自行運行,然後逐步完成。 – 2014-11-03 23:46:19

回答

1

調試的一個小時後,得到它的工作。我只是必須改變我在DEBUG I中提到的問題(有問題)。我改變它如下:

transitionTable[newStates.get(j)][i]