通过此数据对有限确定性自动机进行建模

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

equal:

            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。

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

编辑：

您需要一个 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);

这应该通过 的初始化方法来实现当然是自动机类。