如何在不使用 reg 表达式的情况下在 Java 中实现 DFA？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20153970/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I implement a DFA in Java without using reg expression?
提问by user3023259
I have this input file :
我有这个输入文件：
2
4
ab
1 0 2 0 3 0 3 3
0
1 3
aaa
bbaaab
abab
zzz
7
ab
2 1 3 0 4 3 5 2 6 5 6 4 6 6
0
1 5
a
aab
baa
bbabbabbb
ababb
ababba
zzz
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.
每个测试用例以 3 个整数开始，第一个是自动机的状态数，接下来是字母表中的符号数，然后是最终状态数。
The next line is the alphabet. The symbols appear together.
下一行是字母表。符号一起出现。
Next is an arbitrary number of lines containing inputs over Σ(alphabet). Each input is a string of characters taken from Σ(alphabet).
接下来是包含 Σ(alphabet) 输入的任意数量的行。每个输入都是从 Σ（字母表）中提取的字符串。
The lines of input are terminated by a final line containing the string zzz.
输入行以包含字符串 zzz 的最后一行终止。
my output should look like this
我的输出应该是这样的
DMA M1
aaa: Accepted
bbaaab: Accepted
abab: Rejected
DMA M2
a: Rejected
aab: Accepted
baa: Accepted
bbabbabbb: Accepted
ababb: Accepted
ababba: Rejected
Here is my code thus far :
到目前为止，这是我的代码：
import java.util.Scanner;
import java.lang.String;
public class DFAImplementation {
public static void main(String[] args) throws Exception {
//create the file instance
java.io.File file = new java.io.File("DFA.txt");
//it's scanner time
Scanner input = new Scanner(file);
//read it
int dfaAmount = input.nextInt();
//loop for amount of dfas
for (int dfaAmountIndex = 0; dfaAmountIndex < dfaAmount;
dfaAmountIndex++){
int numberOfStates = input.nextInt();
int startState;
int numberOfSigmaSym;
String sigma = "";
sigma = input.next();
numberOfSigmaSym = sigma.length();
String transitionLine = input.nextLine();
int[][] transition = new int[numberOfStates][numberOfSigmaSym];
startState = input.nextInt();
//checker
System.out.println(startState);
int i;
int j;
for (i=0; i < numberOfStates; i++){
numberOfStates = i;
numberOfSigmaSym = j;
for (j=0; j < sigma.length(); j++){
int state1 = transition[i][j];
}
}
String w;
w = input.nextLine();
for (i=0; i < w.length(); i++){
char x;
x = w.charAt(i);
int state = startState;
int index = sigma.indexOf(x);
int state1 = transition [state][index];
}
int numberOfAcceptStates;
numberOfAcceptStates = input.nextInt();
int acceptState;
acceptState = input.nextInt();
// if(){
}
// else(){
}
}
//}
--Edit: Basically I just don't know what to do with my transition array and states.
--编辑：基本上我只是不知道如何处理我的转换数组和状态。
回答by Doswell
looking at the first example starting at 0 for aaa would move as; 0 (a)-> 1 (a)-> 2 (a)-> 3 and 3 is a valid end state, similar for bbaaab; 0 (b)-> 0 (b)-> 0 (a)-> 1 (a)-> 2 (a)-> 3 (b)-> 3
查看从 0 开始 aaa 的第一个示例将移动为；0 (a)-> 1 (a)-> 2 (a)-> 3 和 3 是有效的结束状态，类似于 bbaaab；0 (b)-> 0 (b)-> 0 (a)-> 1 (a)-> 2 (a)-> 3 (b)-> 3
So it might be easier to read the states into an object which has an array or hashtable of the alphabet and the next state that letter goes to.
因此，将状态读入一个对象中可能更容易，该对象具有字母表的数组或哈希表以及该字母的下一个状态。
Than for each letter in the line move to the next state, ie;
比对于行中的每个字母移动到下一个状态，即；
int currentState = 0;
for (i=0; i<w.length();i++)
currentState = states[currentState].nextState(w.charAt(i))
Where states is something like;
状态就像这样;
State[] states;
And State is something like;
状态是这样的；
Hashtable<Integer, Integer> nextStates;
public int nextState(char letter) {
return nextStates.get(Integer.valueOf(letter));
}
Then after check if current state is a valid end state.
然后在检查当前状态是否是有效的结束状态之后。
