このオートマトンシミュレーターで状態から次の状態に移動するために、このメソッドを使用しています。
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);
}
}
}
ここ：
State nextState;
nextState = ((State)actualState.get(characterToProcess));
私は何か間違ったことをしているかもしれませんが、私はそれを理解していません。
StringBuilderは正しく処理されていますが、オートマトンは常に状態0でスタックします。なぜですか？
完全なコードは次のとおりです。
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);
}
}
}
}
入力ファイルは次のとおりです。
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
編集：ここでは、この入力ファイルの形式について説明します
最初の行は、テストケースの数を表しています。
各テストケースは3つの整数で始まり、最初はオートマトンの状態の数、次はアルファベットの記号の数、次に最終状態の数です。
次の行はアルファベットです。シンボルは一緒に表示されます。
次に、遷移関数を説明する状態の数に等しい行数があります。この行グループの最初の行は、オートマトン（qo）の最初の状態の遷移関数を表し、最初の要素は、アルファベットの最初の記号がこの状態になったときに到達した状態を表します。元の問題ステートメントからこれを理解するのに苦労しました。これは私がそれを見に来た最も簡単な方法です：
台詞：
1 0
2 0
2 0
同等：
AlphabetSymbol0 AlphabetSymbol1
State0 State1 State0
State1 State2 State0
State2 State2 State0
次に、オートマトンの最終状態を示す行があります。
次に、初期状態と入力文字列の数を示す行が表示されます。
次に、入力文字列の行が表示されます。
このプログラムの出力は次のようになります。
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**
太字で書かれているすべての行が間違っています。
私が得ている：
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
私のオートマトンはすべてを受け入れて状態0でスタックしています、なぜですか？