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 クラスを作成する必要がありますか? 単純に配列を使用する必要がありますか? 配列にどのようなロジックを適用しますか?

編集これは、マイケル・ボルグワードのアドバイスに従って私が作成したコードです。トランジションは機能しますが、処理中に文字列が状態 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

最も自然な表現は、Mapアルファベット記号をキーとして各状態を としてモデル化し、結果の状態 (Mapインスタンス) を値としてモデル化することです。オートマトンを表すクラスには、初期状態の参照、現在の状態の参照、状態の参照、SetおよびSet最終状態の参照があります。ああ、Setアルファベットの a です。

上記により、関連するすべての操作で優れたパフォーマンスが得られるはずです。利便性とカプセル化のためにいくつかのメソッドを追加すれば完了です。

編集：

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...

このような単純なものがある場合は、コードが分離され、一度に1つのセクション（入力を解析してFSMに渡す「UI」セクション）を簡単に考えることができます。些細なことになるはずです）これはあなたが実際に尋ねた質問を残すだけです：FSMを実装する方法。

おそらく百万通りの方法がありますが、参照して操作するのが最も簡単なのはint[][]である必要があると思います。遷移構文は、次のように明確でわかりやすくなります。

newState=table[oldState][transition];

アレイにデータを入力したら。

ただし、コードを分解して、コードの次のステップだけでなく、クラスにアクセスする方法を考えることを忘れないでください。

于 2009-12-09T00:35:30.410 に答える