java - 通过 HashMap 在该自动机中从一个状态移动到另一个状态

Question

我正在使用此方法在此自动机模拟器上从一个状态移动到下一个状态:

public void processString (String string){


StringBuilder stepString= new StringBuilder (string);


int actualStateIntIndex;





 System.out.println("THE FOUND INITIAL ONE IS "+ theInitialStateIntIndex);


   State firstState = allStates.get(theInitialStateIntIndex);

  actualState = firstState;

   while (stepString.length()>0){

       Character characterToProcess = stepString.charAt(0);
       stepString.deleteCharAt(0);

       State nextState;
       nextState = ((State)actualState.get(characterToProcess)); // pasa al siguiente State
   actualState = nextState;

   actualStateIntIndex=allStates.indexOf(actualState);


   System.out.println("the actual state for " + stepString + " is " + actualStateIntIndex);

   if ((actualState.isFinal==true) && (stepString.length()==0))
      {
          System.out.println("THE STRING " + string + " IS ACCEPTED AT STATE " + actualStateIntIndex );

      }

   else if (stepString.length()==0 && (actualState.isFinal==false)){
          System.out.println("THE STRING " + string + " IS REJECTED AT STATE " + actualStateIntIndex);

      }

   }

}

这里:

State nextState;
nextState = ((State)actualState.get(characterToProcess)); 

我可能做错了什么，但我不明白。

虽然 StringBuilder 正在正确处理，但自动机总是卡在状态 0，为什么？

完整代码如下:

       package afd;

        import java.io.*;
        import java.util.*;

        /**
         *
         * @author Administrator
         */
        public class Main {

        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) throws IOException {
            // TODO code application logic here

            FileReader fr = new FileReader("E://Documents and Settings//Administrator//My Documents//NetBeansProjects//AFD//src//afd//dfa.in");


            BufferedReader br = new BufferedReader(fr);

            String firstLine= br.readLine();


            String [] firstLineSplitted = firstLine.split(" ");

            /*debug*/
            //System.out.println("firstLine is " + firstLine);

            int numberOfTestCases = Integer.parseInt(firstLine);

            for (int indexOfTestCases =0; indexOfTestCases < numberOfTestCases; indexOfTestCases++  ){

                int aux;
                System.out.println("Case Number " +  (aux = indexOfTestCases+1));

                String caseStartLine = br.readLine();

                /*debug*/
                //System.out.println("caseStarLine is " + caseStartLine);
                String [] caseStartLineSplitted = caseStartLine.split(" ");

                int numberOfStates;
                int numberOfAlphabetSymbols;
                int numberOfFinalStates;


                numberOfStates = Integer.parseInt(caseStartLineSplitted[0]);

                numberOfAlphabetSymbols = Integer.parseInt(caseStartLineSplitted[1]);

                numberOfFinalStates = Integer.parseInt(caseStartLineSplitted[2]);




                Automaton automaton = new Automaton();


                automaton.setAllStates(numberOfStates);

      //          automaton.size = numberOfStates;
     //           automaton.numberOfAlphabetSymbols = numberOfAlphabetSymbols;
     //           automaton.numberOfFinalStates = numberOfFinalStates;
                //Automaton a = new Automaton(numberOfStates);


                String alphabetLine = br.readLine();
                System.out.println("alphabetLine is " + alphabetLine);

                automaton.setAlphabet (alphabetLine);

    //            automaton.alphabetSymbols =new StringBuffer(alphabetLine);

                for (int indexOfStates = 0; indexOfStates < numberOfStates; indexOfStates++){

                      String transitionsLine = br.readLine();
                       /*debug*/
                       System.out.println("for the state " + indexOfStates + " transitionsLine is " + transitionsLine);

                       automaton.setTransitions(indexOfStates,transitionsLine);

                      /*String [] ijLineSplitted = ijLine.split(" ");

                      int i = Integer.parseInt(ijLineSplitted[0]);
                      int j = Integer.parseInt(ijLineSplitted[1]);
                        */

                }

                String finalStatesLine = br.readLine();
                /*debug*/
                System.out.println("finalStatesLine is " + finalStatesLine);
                String finalStatesLineSplitted [] = finalStatesLine.split(" ");

                automaton.markFinalStates(finalStatesLineSplitted);



                String initialStateAndNumberOfStringsLine = br.readLine();

                /*debug*/
                //System.out.println("initialStateAndNumberOfStringsLine  is " +initialStateAndNumberOfStringsLine);
                String [] splittedInitialStateLine = initialStateAndNumberOfStringsLine.split(" ");

                int initialState = Integer.parseInt(splittedInitialStateLine[0]);
                int numberOfStrings = Integer.parseInt(splittedInitialStateLine[1]);

                automaton.markInitialState(initialState);

                for (int stringIndex =0; stringIndex<numberOfStrings; stringIndex++){

                     String stringToProcess = br.readLine();
                     /*debug*/
                System.out.println("stringToProcess is " + stringToProcess);

                    automaton.processString(stringToProcess);


                }


             }
            }







    }


    class State extends HashMap<Character, State>{

    boolean isFinal;
    boolean isInitial;
    int stateId;

    State () {
        isInitial=false;
        isFinal = false;

        }

    public boolean equals (Object o){




        boolean isEqual = false;

        State compare = (State)o;

        if ((compare.stateId)==this.stateId)
        {

            return true;
        }

        return isEqual;

    }

    public int hashCode() {

        int theHashCode = stateId%7;

        return theHashCode;

    }


    }

      class Automaton{
         List <State> allStates;
        //private List<State> finalStates;
         int  theInitialStateIntIndex;
         State actualState;
          char [] alphabet;




        Automaton() {


            allStates = new ArrayList<State>();


        }public void setAllStates (int numberOfStates)  {

        for (int i =0; i <numberOfStates; i++) {

            State newState = new State();
            newState.stateId = i;
            allStates.add(newState);

         }

    }


    public void setAlphabet (String alphabetLine){

        alphabet = alphabetLine.toCharArray();




    }

    public void markFinalStates (String [] finalStates){

        for (int index =0; index<finalStates.length; index++) {

            int aFinalStateId = Integer.parseInt(finalStates[index]);

            State aFinalState = allStates.get(aFinalStateId);
            aFinalState.isFinal = true;
            allStates.add(aFinalStateId, aFinalState);


            /*DEBUG*/
            aFinalState = allStates.get(aFinalStateId);
            if ((aFinalState.isFinal)==true)
            System.out.println("THE STATE " + aFinalStateId + " IS MARKED AS FINAL");

        }

    }

    public void markInitialState (int initialStateId) {

            State theInitialState = allStates.get(initialStateId);
            theInitialState.isInitial=true;
            allStates.add(initialStateId, theInitialState);

            theInitialStateIntIndex = initialStateId;

            /*DEBUG*/

            System.out.println("THE INITIAL STATE ID IS " + initialStateId);

            theInitialState = allStates.get(initialStateId);
            if ((theInitialState.isInitial)==true)
            System.out.println("THE STATE " + initialStateId + " IS MARKED AS INITIAL");

    }


    public void setTransitions(int stateId, String transitionsLine){


            State theOneToChange = allStates.get(stateId);

            String [] statesToReachStringSplitted = transitionsLine.split(" ");

            for (int symbolIndex=0; symbolIndex<statesToReachStringSplitted.length;symbolIndex++){

                int reachedState= Integer.parseInt(statesToReachStringSplitted[symbolIndex]);

                theOneToChange.put(alphabet[symbolIndex],allStates.get(reachedState));

                System.out.println("THE STATE " + stateId + " REACHES THE STATE " + reachedState + " WITH THE SYMBOL " + alphabet[symbolIndex]);

            }

            allStates.add(stateId, theOneToChange);

    }


    public int findInitialState(){


        int index =0;

       cycle: for (; index<allStates.size(); index++){

            State s = allStates.get(index);

            if (s.isInitial==true) {

                break cycle;



           }
        } return index;

}



    public void processString (String string)
    {


        StringBuilder stepString= new StringBuilder (string);


        int actualStateIntIndex;



       System.out.println("THE FOUND INITIAL ONE IS "+ theInitialStateIntIndex);


       State firstState = allStates.get(theInitialStateIntIndex);

      actualState = firstState;

       while (stepString.length()>0){

           Character characterToProcess = stepString.charAt(0);
           stepString.deleteCharAt(0);

           State nextState;
           nextState = ((State)actualState.get(characterToProcess)); // pasa al siguiente State

           actualState = nextState;

           actualStateIntIndex=allStates.indexOf(actualState);


           System.out.println("the actual state for " + stepString + " is " + actualStateIntIndex);

           if ((actualState.isFinal==true) && (stepString.length()==0))
              {
                  System.out.println("THE STRING " + string + " IS ACCEPTED AT STATE " + actualStateIntIndex );

              }

           else if (stepString.length()==0 && (actualState.isFinal==false)){
                  System.out.println("THE STRING " + string + " IS REJECTED AT STATE " + actualStateIntIndex);

              }

           }



       }




    }

这是输入文件:

4
3 2 1
ab
1 0
2 0
2 0
2
0 3
abaa
aab
aba
3 3 2
ade
0 1 2
1 2 0
2 1 0
1 2
2 2
a
de
3 2 1
ab
1 0
2 0
2 0
2
0 3
abaa
aab
aba
3 3 2
ade
0 1 2
1 2 0
2 1 0
1 2
2 2
a
de

编辑:在这里我将解释此输入文件的格式

第一行代表测试用例的数量。

每个测试用例都以 3 个整数开始，第一个是自动机的状态数，接下来是字母表中的符号数，然后是最终状态数。

下一行是字母表。这些符号一起出现。

然后有一些行数等于描述转换函数的状态数。这组行的第一行表示自动机 (qo) 中第一个状态的转换函数，第一个元素表示当字母表中的第一个符号进入该状态时所达到的状态，依此类推。我很难从最初的问题陈述中理解这一点。这是我看到它的最简单的方法:

行:

1 0
2 0
2 0

等于:

            AlphabetSymbol0        AlphabetSymbol1
State0         State1                State0
State1         State2                State0
State2         State2                State0

然后有一行表示自动机的最终状态。

然后是一行，说明哪个是初始状态以及将出现多少个输入字符串。

然后是包含输入字符串的行。

该程序的输出应该是:

C

ase Number 1
alphabetLine is ab
for the state 0 transitionsLine is 1 0
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 1 transitionsLine is 2 0
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 2 transitionsLine is 2 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL b
finalStatesLine is 2
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 0
THE STATE 0 IS MARKED AS INITIAL
stringToProcess is abaa
THE FOUND INITIAL ONE IS 0
the actual state for baa is 0
the actual state for aa is 0
the actual state for a is 0
the actual state for  is 0
**THE STRING abaa IS ACCEPTED AT STATE 2**
stringToProcess is aab
THE FOUND INITIAL ONE IS 0
the actual state for ab is 0
the actual state for b is 0
the actual state for  is 0
**THE STRING aab IS REJECTED AT STATE 0**
stringToProcess is aba
THE FOUND INITIAL ONE IS 0
the actual state for ba is 0
the actual state for a is 0
the actual state for  is 0
**THE STRING aba IS ACCEPTED AT STATE 1**
Case Number 2
alphabetLine is ade
for the state 0 transitionsLine is 0 1 2
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 0 REACHES THE STATE 2 WITH THE SYMBOL e
for the state 1 transitionsLine is 1 2 0
THE STATE 1 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL d
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL e
for the state 2 transitionsLine is 2 1 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL e
finalStatesLine is 1 2
THE STATE 1 IS MARKED AS FINAL
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 2
THE STATE 2 IS MARKED AS INITIAL
stringToProcess is a
THE FOUND INITIAL ONE IS 2
the actual state for  is 0
**THE STRING a IS ACCEPTED AT STATE 2** 
stringToProcess is de
THE FOUND INITIAL ONE IS 2
the actual state for e is 0
the actual state for  is 0
**THE STRING de IS REJECTED AT STATE 0** 

我把所有粗体的行都弄错了。

我得到:

Case Number 1

THE STRING abaa IS ACCEPTED AT STATE 0
THE STRING aab IS ACCEPTED AT STATE 0
THE STRING aba IS ACCEPTED AT STATE 0


Case Number 2
THE STRING a IS ACCEPTED AT STATE 0
THE STRING de IS ACCEPTED AT STATE 0

我的自动机正在接受一切并卡在状态 0，为什么？

Answer 1

我很确定问题是 State 需要重写 .equals(Object) 和 .hashCode()。我相信 allStates 是 List<State>并且必须重写该 List equals 上的 get(State) 调用。