有限自动机与建模

前言

　　在学校学程序设计语言的时候，能接触到的所有例子没有一个跟现实世界是有关系的。大多是关注于语言的细节层次，根本没有模型的概念，而我认为，要真正的让别人理解模型是如何建立的，最好的方法是从一个实实在在的东西开始，逐步的建立一个与物理世界可以有对应关系的模型出来。那样，在以后的实践中，可以很轻易的对未知的对象进行数学建模。OO最大的特点并非继承，多态等概念，而是与物理世界建立对应的关系！

　　选择有限自动机作为例子来说，有这样几点考虑：

　　有限自动机几乎是最简单的数学模型，也就是说，它本身就是一个对象

　　这个东西是计算理论中的一个比较核心的东西，也很有意思

　　有限自动机的形式化定义很明了，很精确，也很简单

　　当然，文章的主要目的不是要说有限状态机的计算能力，我们要关注的是如何从例子中掌握建模的基本方法。好吧，开始了：

　　有限自动机

　　有限自动机是一种抽象出来的机器，其描述能力和资源(存储)都比较有限。其用途十分广泛，特别在机电一体化中有很多地方用到，而有穷自动机和马尔可夫链的结合是当今模式识别的基础(语音识别，光学字符识别等)。

　　有限自动机的形式化定义很简单，是一个5元组(Q, Σ, δ, q0, F),其中

　　Q是一个有穷集合，称为状态集，定义了自动机所有的状态

　　Σ是一个有穷集合，称为字母表

　　δ是一个转移函数，Q×Σ -> Q

　　q0∈Q 是其实状态

　　F⊆Q 是接受状态集(可以有多个接受状态s)

　　也就是说，以上几点唯一的确定一个有限自动机，自动机会有两个最终状态，接受或拒绝。

　　建立模型

　　好，开始建立模型：

首先，我们应该有一个用来描述有限自动机的对象，这个对象有接受输入，进行运算，得出结论等操作。当然，有限自动机也有很多种，确定型的和非确定型的，只要涉及到很多种具有共性的，我们一般会抽象出共性来做接口。

　　其次，我们可以看到，整个形式化定义都是基于集合的，我们应该有一个用以描述集合的对象，这个对象上可以进行添加元素，获取元素，删除元素，获取集合的大小等操作。

　　集合中是什么东西呢? 可以看到有状态，有字母表，我们可以考虑设计一个基类(元素)，基类上可以拿到元素的真实值。

　　这个转移函数如何表示? δ实际上是一个矩阵，类似于数字电子中的真值表，因此我们需要有一个对象来表示这个转移函数，这个对象可以根据当前状态和输入字符来查出一个新的状态来(这就是它为什么叫转移函数的原因)。

　　抽象到这个粒度，可以看出整个系统中的所有对象我们都可以表示了，然后我们可以对这些对象进行适当的简化：

　　先看看自动机的接口：

package　algorithm.machine;

/**
　*　
　*　@author　juntao.qiu
　*/
public　interface　StateMachine　{
　　　　/**
　　　　　*　start　the　state　machine
　　　　　*/
　　　　public　void　start();
　　　　
　　　　/**
　　　　　*　set　the　string　to　evaluate
　　　　　*　@param　string　the　<code>string</code>　to　be　evaluate
　　　　　*/
　　　　public　void　input(String　string);
　　　　
　　　　/**
　　　　　*　check　whether　the　<code>string</code>　is　accepted　by　state　machine
　　　　　*　@return
　　　　　*/
　　　　public　boolean　isAccept();
}

　集合的接口：

package　algorithm.machine;

/**
　*
　*　@author　juntao.qiu
　*/
public　interface　Set　{
　　　　/**
　　　　　*　add　a　new　element　into　set
　　　　　*　@param　element
　　　　　*/
　　　　public　void　add(Element　element);
　　　　
　　　　/**　
　　　　　*　get　a　element　by　its　index
　　　　　*　@param　index
　　　　　*　@return
　　　　　*/
　　　　public　Element　get(int　index);
　　　　
　　　　/**
　　　　　*　get　the　size　of　the　set
　　　　　*　@return　size　of　the　set
　　　　　*/
　　　　public　int　size();
　　　　
　　　　/**
　　　　　*　check　if　the　set　has　element　<code>e</code>
　　　　　*　@param　e
　　　　　*　@return
　　　　　*/
　　　　public　boolean　hasElement(Element　e);
}

　　集合中元素的接口：

package　algorithm.machine;

public　interface　Element　{
　　　　/**
　　　　　*　get　the　real　value　of　an　element
　　　　　*　@return
　　　　　*/
　　　　public　String　getValue();
}

　　转移函数：

package　algorithm.machine;

public　interface　Matrix　{
　　　　/**
　　　　　*　get　the　value　while　x　is　an　element　of　State-Set,　and
　　　　　*　an　element　of　Epsilon-Set
　　　　　*　@param　x　an　element　of　<code>StateSet</code>
　　　　　*　@param　y　an　element　of　<code>EpsilonSet</code>
　　　　　*　@return
　　　　　*/
　　　　public　Element　getElementAt(Element　x,　Element　y);
}

 

接口是最简洁的抽象层次，可以从接口中很清晰的看出整个系统的结构来，所以这里只给出接口的定义，源码可以给出下载链接。

　　测试

　　我们来看看Main中的测试，然后就可以知道为什么要这样抽象，这样建模，main中是整个系统运行的脉络，如果接口定义的比较合理，清晰，那么代码读起来会很流畅，希望下面的代码读起来比较流畅，呵呵。

　　　　public　static　void　main(String[]　args){
　　　　　　　　Set　stateSet　=　new　GeneralSet();//建立状态集
　　　　　　　　Set　epsilonSet　=　new　GeneralSet();//建立符号表
　　　　　　　　Set　finalSet　=　new　GeneralSet();//接受状态集
　　　　　　　　
　　　　　　　　stateSet.add(new　State("Q0"));
　　　　　　　　stateSet.add(new　State("Q1"));
　　　　　　　　stateSet.add(new　State("Q2"));
　　　　　　　　
　　　　　　　　epsilonSet.add(new　State("0"));
　　　　　　　　epsilonSet.add(new　State("1"));
　　　　　　　　
　　　　　　　　finalSet.add(new　State("Q1"));//接受状态为Q1
　　　　　　　　
　　　　　　　　/*
　　　　　　　　　*　The　transfer　matrix
　　　　　　　　　*　　　　　|　0　　1
　　　　　　　　　*　----*--------
　　　　　　　　　*　　Q0　|　Q0　Q1
　　　　　　　　　*　　Q1　|　Q2　Q1
　　　　　　　　　*　　Q2　|　Q1　Q1
　　　　　　　　　*　　　
　　　　　　　　　*/
　　　　　　　　String[][]　tran　=　new　String[][]{
　　　　　　　　　　　　　　　　{"Q0",　"0",　"Q0"},
　　　　　　　　　　　　　　　　{"Q0",　"1",　"Q1"},
　　　　　　　　　　　　　　　　{"Q1",　"0",　"Q2"},
　　　　　　　　　　　　　　　　{"Q1",　"1",　"Q1"},
　　　　　　　　　　　　　　　　{"Q2",　"0",　"Q1"},
　　　　　　　　　　　　　　　　{"Q2",　"1",　"Q1"}
　　　　　　　　};
　　　　　　　　
　　　　　　　　TransferMatrix　matrix　=　new　TransferMatrix(tran);//定义转移函数表
　　　　　　　　//根据5元组构造一个状态机
　　　　　　　　StateMachine　machine　=　new　FiniteStateMachine(
　　　　　　　　　　　　　　　　stateSet,　epsilonSet,matrix,new　State("Q0"),finalSet);
　　　　　　　　
　　　　　　　　machine.input("0100010101011");//在状态机上进行输入
　　　　　　　　machine.start();//开始计算
　　　　　　　　//判断是否被接受
　　　　　　　　if(machine.isAccept()){
　　　　　　　　　　　　System.err.println("string　is　accepted");
　　　　　　　　}else{
　　　　　　　　　　　　System.err.println("string　is　not　accepted");
　　　　　　　　}
　　　　}

　　P.S. 本来要插入几张图片的，不知道为什么编辑到一半的时候插入图片老是插不进去，出来的对话框不知道怎么上传本地的图片。