2

我有这个输入文件：

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

              }

           }



       }




    }
4

2 回答 2

3

我想说最自然的表示是将每个状态建模为 a Map，其中字母符号作为键，结果状态（即Map实例）作为值。表示自动机的类将具有初始状态的引用、当前状态的引用、状态的SetaSet和最终状态的 a。哦，还有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类的初始化方法来实现。

于 2009-12-08T23:20:37.940 回答
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];

一旦你填充了数组。

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

于 2009-12-09T00:35:30.410 回答