通过该数据建模有限确定性自动机 [英] Modelling a Finite Deterministic Automaton via this data
问题描述
我有这个输入文件：
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.
每个测试用例以3个整数开始，第一个是自动机的状态数，接下来是字母表中符号的数量，然后是最终状态的数量。
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.
然后有许多行等于描述转换函数的状态数。这组线的第一行表示自动机中第一个状态的转换函数（qo），第一个元素表示当字母表中的第一个符号进入此状态时达到的状态，依此类推。我从最初的问题陈述中理解这一点很困难。这是我最容易看到的方式：
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:
行：
1 0
2 0
2 0
相等：
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.
此程序的输出应为：
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.
我不知道如何最方便地表示自动机。我应该创建一个Graph类吗？我应该只使用数组吗？我将对阵列应用什么逻辑？
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?
编辑这是我在迈克尔·博尔沃特的建议之后制作的代码。
过渡工作但我不知道为什么线索在加工时会收到状态0
**
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);
}
}
}
}
推荐答案
我会这么说最自然的表示是将每个州建模为 Map ，其中字母符号为键和结果状态（即 Map 实例）作为价值观。表示自动机的类将具有初始状态的引用，一个用于当前状态，一个 Set 状态和一个 Set 最终状态。哦，以及字母表中的设置。
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.
编辑：
您需要一个州类才能正确使用泛型：
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
}
对于您使用的3状态自动机示例：
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);
这应该通过ini实现当然， Automaton 类的tialization方法。
This should happen through initialization methods of the Automaton class, of course.
这篇关于通过该数据建模有限确定性自动机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
