I'm using this method to move from a state to the next on this automaton simulator:
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);
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);
}
}
}
Here:
State nextState;
nextState = ((State)actualState.get(characterToProcess));
I might be doing something wrong, but I don't get it.
The automaton gets stuck on state 0 always, although the StringBuilder is correctly being processed, why?
Here's the full code:
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++ ){
int aux;
System.out.println("Case Number " + (aux = indexOfTestCases+1));
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("for the state " + indexOfStates + " 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;
int stateId;
State () {
isInitial=false;
isFinal = false;
}
public boolean equals (Object o){
boolean isEqual = false;
State compare = (State)o;
if ((compare.stateId)==this.stateId)
{
return true;
}
return isEqual;
}
public int hashCode() {
int theHashCode = stateId%7;
return theHashCode;
}
}
class Automaton{
List <State> allStates;
//private List<State> finalStates;
int theInitialStateIntIndex;
State actualState;
char [] alphabet;
Automaton() {
allStates = new ArrayList<State>();
}public void setAllStates (int numberOfStates) {
for (int i =0; i <numberOfStates; i++) {
State newState = new State();
newState.stateId = i;
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);
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);
}
}
}
}
Here's the input file:
4
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 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
Edit: Here I'll explain the format for this input file
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:
C
ase Number 1
alphabetLine is ab
for the state 0 transitionsLine is 1 0
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 1 transitionsLine is 2 0
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL b
for the state 2 transitionsLine is 2 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL b
finalStatesLine is 2
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 0
THE STATE 0 IS MARKED AS INITIAL
stringToProcess is abaa
THE FOUND INITIAL ONE IS 0
the actual state for baa is 0
the actual state for aa is 0
the actual state for a is 0
the actual state for is 0
**THE STRING abaa IS ACCEPTED AT STATE 2**
stringToProcess is aab
THE FOUND INITIAL ONE IS 0
the actual state for ab is 0
the actual state for b is 0
the actual state for is 0
**THE STRING aab IS REJECTED AT STATE 0**
stringToProcess is aba
THE FOUND INITIAL ONE IS 0
the actual state for ba is 0
the actual state for a is 0
the actual state for is 0
**THE STRING aba IS ACCEPTED AT STATE 1**
Case Number 2
alphabetLine is ade
for the state 0 transitionsLine is 0 1 2
THE STATE 0 REACHES THE STATE 0 WITH THE SYMBOL a
THE STATE 0 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 0 REACHES THE STATE 2 WITH THE SYMBOL e
for the state 1 transitionsLine is 1 2 0
THE STATE 1 REACHES THE STATE 1 WITH THE SYMBOL a
THE STATE 1 REACHES THE STATE 2 WITH THE SYMBOL d
THE STATE 1 REACHES THE STATE 0 WITH THE SYMBOL e
for the state 2 transitionsLine is 2 1 0
THE STATE 2 REACHES THE STATE 2 WITH THE SYMBOL a
THE STATE 2 REACHES THE STATE 1 WITH THE SYMBOL d
THE STATE 2 REACHES THE STATE 0 WITH THE SYMBOL e
finalStatesLine is 1 2
THE STATE 1 IS MARKED AS FINAL
THE STATE 2 IS MARKED AS FINAL
THE INITIAL STATE ID IS 2
THE STATE 2 IS MARKED AS INITIAL
stringToProcess is a
THE FOUND INITIAL ONE IS 2
the actual state for is 0
**THE STRING a IS ACCEPTED AT STATE 2**
stringToProcess is de
THE FOUND INITIAL ONE IS 2
the actual state for e is 0
the actual state for is 0
**THE STRING de IS REJECTED AT STATE 0**
I'm getting wrong all the lines written in bold.
I'm getting:
Case Number 1
THE STRING abaa IS ACCEPTED AT STATE 0
THE STRING aab IS ACCEPTED AT STATE 0
THE STRING aba IS ACCEPTED AT STATE 0
Case Number 2
THE STRING a IS ACCEPTED AT STATE 0
THE STRING de IS ACCEPTED AT STATE 0
My automaton is accepting everything and getting stuck on state 0, why?