java通过该数据为有限确定性自动机建模

Question

我有这个输入文件：

2
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

然后有一条线显示了自动机的最终状态

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

然后是带有输入字符串的行

该程序的输出应为：

Case #1:
accept 2
reject 0
reject 1
Case #2:
accept 2
reject 0

它应该说明字符串是被接受还是被拒绝，以及它在哪个状态结束

到目前为止，我只使用输入对工作进行了编码

我不知道如何表示自动机最方便我应该创建一个Graph类吗？我应该简单地使用数组吗？我将对阵列应用什么逻辑

编辑这是我按照MICHAEL BORGWARDT的建议编写的代码。 转换工作正常，但我不知道为什么在处理字符串时，字符串会卡在状态0上 **

  /*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

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++  ){



            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("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;

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

}

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




    Automaton() {


        allStates = new ArrayList<State>();


    }

    public void setAllStates (int numberOfStates)  {

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

            State newState = new State();
            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);

       State 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);

              }

           }



       }




    }

Answer 1

这是一个有趣的项目

您可能需要首先考虑FSM周围的接口。你是如何编程的？你怎么喂它

比如：

fsm.setStates("ab");
fsm.setInitialState(0);
fsm.addTransition(1,0);
fsm.addTransition(2,0);
fsm.addTransition(2,0);
fsm.setFinalState...

如果你有这样简单的东西，它会把你的代码分离出来，让你一次只想一个部分（你的“UI”部分，解析输入并将其传递给FSM，应该变得很简单）这就留下了你实际要问的问题：如何实现FSM

可能有一百万种方法，但我认为最容易引用和使用的是int[]；转换语法将清晰明了，如下所示：

newState=table[oldState][transition];

填充阵列后

但请记住，要将代码分开，并考虑如何访问这些类，而不仅仅是代码中的下一步是什么

Answer 2

我想说，最自然的表示是将每个状态建模为Map，字母符号作为键，结果状态（即Map实例）作为值。表示自动机的类将有一个初始状态的引用、一个当前状态的引用、一个状态的Set引用和一个最终状态的Set引用。哦，还有一个字母表

以上内容将为您提供所有相关操作的良好性能。添加一些方便和封装的方法，就完成了

编辑：

您需要一个State类才能正确使用泛型：

public class State extends HashMap<Character, State>{ }

public class Automaton{ 
    private Set<State> allStates;
    private Set<State> finalStates;
    private State initialState;
    private State currentState;
    private Set<Character> alphabet;

    public boolean doTransition(Character input)){
        if(!alphabet.contains(input){ 
            throw new IllegalArgumentException();
        }
        if(finalStates.contains(currentState)){ 
            throw new IllegalStateException(); 
        }

        currentState = currentState.get(input);

        if(currentState == null){ 
            throw new IllegalStateException(); 
        }

        return finalStates.contains(currentState);
    }

    // more methods go here
}

对于用作示例的3状态自动机：

State s0 = new State();
State s1 = new State();
State s2 = new State();
s0.put('a', s1);
s0.put('b', s0);
s1.put('a', s2);
s1.put('b', s0);
s2.put('a', s2);
s2.put('b', s0);

当然，这应该通过Automaton类的初始化方法实现