Modelling a Finite Deterministic Automaton via this data

Question

I have this input file:

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

The first line represents the number of test cases.

Each test case starts with 3 integers, the first is the number of state for the automaton, next is the number of symbols in the alphabet and then the number of final states.

The next line is the alphabet. The symbols appear together.

Then there's a number of lines equal to the number of states that describe the transition function. The first line of this group of lines represents the transition function for the first state in the automaton (qo), the first element represents the state that's reached when the first symbol in the alphabet goes to this state, and so on. I had trouble understanding this from the original problem statement. This is the easiest way I've come to see it:

The lines:

1 0
2 0
2 0

equal:

            AlphabetSymbol0        AlphabetSymbol1
State0         State1                State0
State1         State2                State0
State2         State2                State0

Then there's a line that says which are the final states for the automaton.

Then comes a line which says which is the initial state and how many input strings will come.

Then come the lines with the input strings.

The output of this program should be:

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

It should say if the String is accepted or rejected and on which state it ended.

So far, I've only coded the work with the input.

I don't know how would be most convenient to represent the automaton. Should I create a Graph class? Should I simply use arrays? What logic would I apply to the arrays?

EDIT THIS IS THE CODE I'VE PRODUCED FOLLOWING MICHAEL BORGWARDT'S ADVICE. THE TRANSITIONS WORK BUT I DON'T KNOW WHY THE STRING GETS STUCK ON STATE 0 WHEN BEING PROCESSED. **

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

              }

           }



       }




    }

Muniment

Answer 1

I'd say that the most natural representation is to model each state as a Map with alphabet symbols as keys and resulting states (i.e. Map instances) as values. A class to represent an automaton would have a reference for the initial state, one for the current state, a Set of states and a Set of final states. Oh, and a Set for the alphabet.

The above should give you good performance for all relevant operations. Add some methods for convenience and encapsulation and you're done.

Edit:

You need a State class to be able to use generics correctly:

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
}

For the 3 state automaton you used as example:

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

This should happen through initialization methods of the Automaton class, of course.

Pope

I think this is a good idea, but I'm not familiar with Maps in Java, can you give a little code snippet for a 3 state automaton? – Muniment

That seems great. Given the String abaa, how would I go through the states? – Muniment

I've added a method to do transitions, you should be able to do the rest on your own. – Pope

I've written new code. Please look at the problem at getting out of state 0. – Muniment

Also, is it necessary for me to override hashCode and equals in State? Why? How should I? – Muniment

The superclass AbstractMap already implements hashCode and equals in a useful manner. Having them is necessary if you want to use instances of the class as keys in a HashMap or elements in a HashSet (equals is used for may other purposes as well). – Pope

Answer 2

That is a fun project.

You might want to think about the interface around your FSM first. How do you program it? How do you feed it?

Something like:

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

If you have something simple like this, it'll separate your code out and make it much easier for you to think of just one section at a time (your "UI" section, which is parsing the input and passing it to the FSM, should become trivial) This just leaves the question you ACTUALLY asked: how to implement the FSM.

There are probably a million ways, but I think the easiest to reference and work with has to be an int[][]; the transition syntax will be clear and straight forward like:

newState=table[oldState][transition];

once you've populated the array.

But remember to break your code apart and think of how you want to access the classes, not just what's the next step in the code.

Anhwei