有限自动机包括有限自动机(DFA )和不确定有限自动机。 这里介绍确定DFA，也就是有限自动机。
1. DFA的形式定义形式上，有限状态机器人可以通过以下五个参数定义：
Q:状态q0，q1，qN的有限集合:有限的输入符号字母q0:初始状态F:终极状态的集合，fq(q，I ) :状态之间的转移函数或转移矩阵。 给定一个状态qQ和一个输入符号I，则(q，I )返回新的状态q'Q。 2.DFA的java实现这里定义了抽象的父类FA，DFA和NFA继承了FA类。
publicabstractclassfa { protectedlistfastateacceptingstates； //可接收状态(结束状态) protected ListFAState states； //所有状态受保护的列表应用程序； //符号字母//状态转移矩阵(使用相邻链表表示) protectedlistlisttransitmatelementstatetransitionmat； //publicclassdfaextendsfa { protectedfastatestartstate； //开始状态}以上是对应于自己安装的DFA的类实例变量的定义。 其中，FAState类表示包含实例属性id的状态节点。
用于唯一区分一个FAState。
创建DFA对象时，需要特定格式的文本文件的路径。
的文件格式。 示例：
5 3
1 2 3 4 5
b a！
1
5
1 -1 -1
-1 2 -1
-1 3 -1
-1 3 4
-1 -1 -1
其中，第一行中的两个数字分别表示机器人的状态数量和符号字母符号的数量
第二行的数字是各状态的id
第三行为符号串(符号串之间用空格分隔) ) ) ) ) ) ) )。
第四行的数字是开始状态的id
第五行的数字是结束状态的id
最后几个工作状态转移矩阵。 其中，数字表示目标状态的状态列表的后缀，-1表示一个状态不能遇到对应的符号。)
上例所示的DFA对象如下图所示为：
3 .使用DFA识别符号串的DFA完成后，可以使用它识别符号串。 这里引用了NFA/DFA算法-摊贩杂货店的一例：
如何通过设计状态及其迁移方法实现分析器呢？ 当然，如果字符串只包含a或b，则分析器只有四种状态。
“奇数a奇数b”、“奇数a偶数b”、“偶数a奇数b”、“偶数a偶数b”。 这些状态依次命名为aa、aB、aB、aB。 大写字母表示偶数，
小写字母表示奇数。 工作还没有开始时，分析器已经读取的字符串必须是空字符串，当然开始状态必须是AB。 当分析器读完一切后
对于字符，如果读取的字符串中的a和b的数量为偶数，则结束的状态也应该是AB。 所以我们展示了这样的状态图：
图3.1检查字符串是否由偶数个a和偶数个b构成的状态图
在该状态图中，短箭头表示AB，AB表示初始状态。 AB的状态有粗边缘，表示AB这一状态
结束的可接受的状态。 一个状态图的结束状态可以是一个或多个。 在本例中，开始状态和结束状态正好相同。
带字符“a”的箭头从AB指向AB，分析器
处于状态AB并且读入的字符是a的话，就转移到状态aB上。我们把这个状态图应用在两个字符串上，分别是”abaabbba”和”aababbaba”。
其中，第一个字符串是可以接受的，第二个字符串是不可接受的(因为有5个a和4个b)。
分析第一个字符串的时候，状态机所经过的状态是：
AB[a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB
分析第二个字符串的时候，状态机所经过的状态是：
AB[a]aB[a]AB[b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB[a]aB
第一个字符串”abaabbba”让状态机在状态AB上停了下来，于是这个字符串是可以接受的。第二个字符串”aababbaba”让状态机
在状态aB上停了下来 ，于是这个字符串是不可以接受的。
DFA识别符号串的核心算法实现如下:
/** * 使用自动机识别符号串 * @param words 待匹配符号串 * @return 如果接受，则返回true,否则，返回false */public boolean recognize(String[] words) {FAState currentState = this.startState;int countOfWordsRecognized = 0;while(countOfWordsRecognized <= words.length) {if(isAccepted(currentState, countOfWordsRecognized, words.length)) { //接收return true;} else if(wordsTerminatedButNotAccepted(currentState, words.length,countOfWordsRecognized)) {return false;}// 当前待识别的单词在alphabet中的下标int indexOfAlpha = alphabet.indexOf(words[countOfWordsRecognized]);//查找状态转移矩阵，获取将要跳转到的状态的下标int transition = getIndexOfStateToSwitch(states.indexOf(currentState), indexOfAlpha);if(transition == -1) {//不能匹配当前符号串，拒绝return false;} else {currentState = this.states.get(transition); //进行下一个符号串的接收countOfWordsRecognized++;}}return false;}4.DFA最小化 4.1 最小状态DFA的含义
1.没有多余状态(死状态)
2. 没有两个状态是互相等价（不可区别）
兼容性（一致性）条件——同是终态或同是非终态
传播性（蔓延性）条件——从s出发读入某个a和从t出发经过某个a并且经过某个b到达的状态等价。
下面就以如下图所示的DFA对象为例说明最小化DFA的操作
DFA的最小化
1. 将状态列表S中的状态分为两个子集:终结状态s1(也叫可接受状态)和非终结状态s2
对于上图中的DFA, s1 = {4, 5, 6, 7}, s2 = {1, 2, 3}
2. 查看s2 = {1, 2, 3}是否可以继续划分
状态2遇到a转向s1中的状态4,不在s2中，于是将s2继续划分，分为{1, 3}和{2}这两个集合。
继续查看{1, 3}是否可以继续划分。由于3遇到b转向s1中的状态5,于是将{1, 3}继续划分，分为{1}和{3}这两个集合。
3. 查看 s1= {4, 5, 6, 7}是否可以继续划分
需要注意的是，当最终所以的子集不可再分时，如果一个子集内的状态不止一个，则由于同一子集内的状态等价，
同一子集内的节点之间的状态跳转可以不用考虑。但是如果这个子集内的某一状态遇到一个符号转向本身时，
这种向自身的转移要体现在新的替换的状态上。例如4,5,6,7最终属于同一子集，最终用节点4来替换这4个节点时，
需要在状态转移矩阵中加上遇到a跳转到节点4，与遇到b跳转到节点4的情况。
最终得到的最小化DFA如下图所示:
DFA最小化的核心算法如下:
/** * 最小化当前DFA对象 */public void simplify() {//用于存放最小化的过程中产生的状态划分List<List<FAState>> stateLists = new ArrayList<List<FAState>>();// phrase 1: 将化简前的DFA的状态分为非可接受状态和可接受状态两部分List<FAState> nonTerminalStates = new ArrayList<FAState>();List<FAState> copyOfOriginalState = deepCloneOfFAStateList(this.states);for(FAState state : copyOfOriginalState) {if(!this.acceptingStates.contains(state)) {nonTerminalStates.add(state);}}List<FAState> terminalStates = deepCloneOfFAStateList(this.acceptingStates);stateLists.add(nonTerminalStates);stateLists.add(terminalStates);// phrase 2: 看nonTerminalStates能否再分,如果可以，则进行划分splitStateListIfCould(stateLists, nonTerminalStates);// phrase 3: 看terminalStates能否再分，如果可以，则进行划分int leftMostEndStateIndex = splitStateListIfCould(stateLists, terminalStates);// phrase 4: 根据存储状态列表的列表的每一个元素作为一个状态，构造最小化DFArebuildDFAWithSimplifiedStateList(stateLists, leftMostEndStateIndex);} DFA的构造以及用于识别符号串，最小化的完整代码可以到http://download.csdn.net/detail/xxc1605629895/7093157下载。
5. 参考资料
1. 正规式->最小化DFA说明 - 碧远|bystander, http://leaver.me/archives/369.html
2. NFA/DFA算法 - 于公摊的杂货铺, http://blog.csdn.net/yukuninfoaxiom/article/details/6057736