`
abruzzi
  • 浏览: 452225 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

有限自动机与建模

阅读更多

前言

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

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

  1. 有限自动机几乎是最简单的数学模型,也就是说,它本身就是一个对象
  2. 这个东西是计算理论中的一个比较核心的东西,也很有意思
  3. 有限自动机的形式化定义很明了,很精确,也很简单

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

有限自动机

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

 

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

  1. Q是一个有穷集合,称为状态集,定义了自动机所有的状态
  2. Σ是一个有穷集合,称为字母表
  3. δ是一个转移函数,Q×Σ -> Q
  4. q0∈Q 是其实状态
  5. 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. 本来要插入几张图片的,不知道为什么编辑到一半的时候插入图片老是插不进去,出来的对话框不知道怎么上传本地的图片。

分享到:
评论
1 楼 lancezhcj 2014-12-17  
有图会直观的多呢,再摸索摸索

相关推荐

    元胞自动机教程 数学建模

    元胞自动机(Cellular Automata,简称CA)是一种在数学建模领域中具有广泛应用的工具。它是一种离散数学模型,能够模拟各种动态系统的演变过程。元胞自动机由大量相同的单元(元胞)组成,这些元胞在离散的时间和...

    数学建模元胞自动机.rar

    这个压缩包“数学建模元胞自动机.rar”包含了关于这一主题的各种资料和PPT,是学习和教学数学建模与元胞自动机的理想资源。 元胞自动机的基本思想是将空间离散化为一系列的单元或“元胞”,每个元胞都具有一定的...

    元胞自动机与实践

    1. **元胞自动机的基本概念**:元胞自动机由一维、二维或更高维度的格子构成,每个格子(元胞)都有一个有限的离散状态。在每个时间步,所有元胞根据相同的、固定的局部规则同时更新其状态。 2. **规则和状态**:...

    元胞自动机用于金融市场建模.pdf

    ### 元胞自动机在金融市场建模中的应用 #### 一、引言 元胞自动机(Cellular Automata, CA)作为一种空间和时间都离散的数学模型,以其简单的规则能够产生复杂行为的特点,在各个领域得到了广泛的应用。在金融市场...

    元胞自动机与Matlab实现

    胞自动机是定义在网格上的,每一个点上的网格代表一个元胞与一种有限的状 态。变化规则适用于每一个元胞并且同时进行。典型的变化规则,决定于元胞的 状态,以及其(4 或 8 )邻居的状态。元胞自动机已被应用于物理...

    论文研究-不确定DNA有限状态自动机在基因网络中的应用 .pdf

    在基因表达网络的建模中,DNA的编码是实现不确定DNA有限状态自动机的关键。DNA编码是将计算机算法中的逻辑操作映射到生物化学过程中的具体操作,例如,将逻辑“on”和“off”状态对应于基因表达的开启和关闭。通过将...

    MATLAB实现元胞自动机【数学建模、科学计算算法】.zip

    元胞自动机(Cellular Automata,简称CA)是一种离散模型,广泛应用于数学建模、物理、生物、计算机科学等多个领域。MATLAB作为一种强大的数值计算和数据可视化工具,是实现元胞自动机的理想平台。这个压缩包"MATLAB...

    元胞自动机优秀论文51

    然后,研究者初步构建了一个随机迁移模型,假定难民在有限的信息下进行迁移决策。通过Matlab进行模拟,虽然得到了主要的迁移路径,但结果与实际数据存在偏差。因此,他们调整了假设,对模型进行了修订。 接下来,...

    数学建模-元胞自动机与Matlab(1).zip

    在“数学建模-元胞自动机与Matlab(1).pdf”这个资料中,我们可以预期学习到以下几个核心知识点: 1. **元胞自动机的基本概念**:理解元胞自动机的定义,包括单元格、状态、邻居和时间步的概念。了解一维、二维及...

    时间自动机 建模和验证工具 UPPAAL

    **时间自动机 UPPAAL:建模与验证的强大工具** UPPAAL(Urban Public Passenger ALgorithm)是一种广泛用于实时系统建模和验证的工具,它基于时间自动机理论,提供了一个集成化环境,用于设计、分析和验证复杂的...

    北京大学自动机理论by金芝老师

    课程可能也涉及了正则表达式与正规集的关系,以及它们如何被有限状态自动机所识别。正则表达式是一种简洁的语法,用于描述一类字符串的集合,而正规集是由所有满足某种规则的字符串组成的集合。正规集可以通过DFA...

    元胞自动机

    元胞自动机因其强大的建模能力而在多个领域得到了广泛应用,尤其是在生态学中,用于预测物种分布、生态系统动态等。本文基于一篇研究文献,探讨了如何利用空间显式元胞模型来评估翡翠梣象(Emerald Ash Borer, EAB)...

    形式语言与自动机理论电子教案

    此外,还会深入探讨识别这些语言的不同模型,如有限状态自动机(FA)、推导树、非确定性有限自动机(NFA)、确定性有限自动机(DFA)、上下文无关文法(CFG)和图灵机(TM)的基本概念和性质。这些模型的构建和理解...

    元胞自动机与MATLAB

    学习元胞自动机与MATLAB结合,不仅可以帮助我们理解复杂系统的演变规律,还可以提高编程和建模能力。通过分析这些M文件,我们可以学习到MATLAB编程技巧,如数组操作、循环结构、条件判断以及图像绘制等。同时,对于...

    基于元胞自动机的单双道交通建模Matlab仿真程序.zip

    元胞自动机(Cellular Automata),简称CA,也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循...

    数学建模模型算法元胞自动机

    由于描述部分提供的内容是百度网盘分享地址,无法提取出与数学建模和元胞自动机相关的知识点,因此不予考虑。而标签部分仅提到了“算法”这一关键词,与元胞自动机紧密相关,因为元胞自动机本身就是一种基于简单规则...

    元胞自动机在数学建模中的应用示例PPT学习教案.pptx

    元胞自动机的特性在于它们是时间和空间上都是离散的,元胞的状态是有限的,且其状态更新依赖于自身的状态和相邻元胞的状态。这种局部交互导致了全局复杂行为的出现,使得元胞自动机在数学建模中有着广泛的应用。 ...

Global site tag (gtag.js) - Google Analytics