这是DFA算法，自己设定好值，看下结果
import java.util.*
import java.io.*
class DFA
{
boolean recognizeString(int move[][], int accept_state[], String word)
{
int s=0
for (int i = 0i <word.length()i++)
{
char c = word.charAt(i)
s = move[s][c - 'a']
}
for (int j = 0j <accept_state.lengthj++)
if (s == accept_state[j]) return true
return false
}
public static void main(String args[]) throws IOException
{
int n, m
BufferedReader in = new BufferedReader(new FileReader("DFA.in"))
StringTokenizer st = new StringTokenizer(in.readLine())
n = Integer.parseInt(st.nextToken())
m = Integer.parseInt(st.nextToken())
while (n != 0)
{
int[][] move = new int[n][m]
for(int i=0i<ni++)
{
st = new StringTokenizer(in.readLine())
for (int j=0j<mj++)
move[i][j] = Integer.parseInt(st.nextToken())
}
String[] temp = in.readLine().split("\\s")
int[] accept = new int[temp.length]
for (int i=0i<accept.lengthi++) accept[i] = Integer.parseInt(temp[i])
String word = in.readLine()
while (word.compareTo("#") != 0)
{
DFA dfa = new DFA()
if (dfa.recognizeString(move, accept, word)) System.out.println("YES")else System.out.println("NO")
word = in.readLine()
}
st = new StringTokenizer(in.readLine())
n = Integer.parseInt(st.nextToken())
m = Integer.parseInt(st.nextToken())
}
}
}
下面具体介绍DFA的化简算法：（1） 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。
K＝K1∪K2
由上述定义知，K1和K2是不等价的。
（2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。
设第i次划分已将状态集划分为k组，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
对于状态集Kj(i)（j=1,2,…,k）中的各个状态逐个检查，设有两个状态Kj’、 Kj’’∈Kj(i)，且对于输入符号a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn属于同一个状态集合，则将Kj’和Kj’’放到同一集合中，否则将Kj’和Kj’’分为两个集合。
（3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。
（4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。
（5） 若有无关状态，则将其删去。
根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。
首先划分终态集和非终态集，之后不断进行划分，直到不再发生变化。每轮划分对所有子集进行。对一个子集的划分中，若每个输入符号都能把状态转换到等价的状态，则两个状态等价。
划分完成后，从每个子集选出一个代表，若DFA中存在两个子集内状态之间的转换，则MFA中两个子集的代表之间也存在对应的转换。简便方法：对每个子集删去除代表以外的状态，并把指向它们的箭弧改为指向代表。
MFA的初态是含有DFA初态的子集的代表。MFA的终态集是DFA终态集划分出来子集的代表。
最后，从MFA中删除从初态无法到达的状态和死状态（只有入射弧或指向自身的出射弧的非终止状态）。
去除不可达状态。建表，行列为不同状态，未标记的格子行列状态等价。首先标记行列一个非终止状态一个终止状态的格子。对未标记的格子(q,q')，若存在一个输入符号a，使q经a到达状态和q'经a到达状态不等价，则标记(q,q')。重复直到表格不再变化。
对于所有未标记的(q,q')，把与q'有关的转换都改到q上，删除q'。
