- 浏览: 444980 次
- 性别:
- 来自: 西安
文章分类
最新评论
-
进退取舍:
谢谢,这个用上了!!
Java 一个线程池的示例 -
pb_water:
感谢楼主,打算买楼主的书,支持一下,楼主功德无量
JavaScript内核系列第0版整理稿下载 -
lancezhcj:
有图会直观的多呢,再摸索摸索
有限自动机与建模 -
hsmsyy:
这里应该是原创了吧,楼主我觉得闭包的作用:实现面向对象。有待商 ...
JavaScript内核系列 第7章 闭包 -
wll52:
在应用退出之前,需要释放连接 con.disconnect() ...
使用smack与GTalk通信
前言
在学校学程序设计语言的时候,能接触到的所有例子没有一个跟现实世界是有关系的。大多是关注于语言的细节层次,根本没有模型的概念,而我认为,要真正的让别人理解模型是如何建立的,最好的方法是从一个实实在在的东西开始,逐步的建立一个与物理世界可以有对应关系的模型出来。那样,在以后的实践中,可以很轻易的对未知的对象进行数学建模。OO最大的特点并非继承,多态等概念,而是与物理世界建立对应的关系!
选择有限自动机作为例子来说,有这样几点考虑:
- 有限自动机几乎是最简单的数学模型,也就是说,它本身就是一个对象
- 这个东西是计算理论中的一个比较核心的东西,也很有意思
- 有限自动机的形式化定义很明了,很精确,也很简单
当然,文章的主要目的不是要说有限状态机的计算能力,我们要关注的是如何从例子中掌握建模的基本方法。好吧,开始了:
有限自动机
有限自动机是一种抽象出来的机器,其描述能力和资源(存储)都比较有限。其用途十分广泛,特别在机电一体化中有很多地方用到,而有穷自动机和马尔可夫链的结合是当今模式识别的基础(语音识别,光学字符识别等)。
有限自动机的形式化定义很简单,是一个5元组(Q, Σ, δ, q0, F),其中
- Q是一个有穷集合,称为状态集,定义了自动机所有的状态
- Σ是一个有穷集合,称为字母表
- δ是一个转移函数,Q×Σ -> Q
- q0∈Q 是其实状态
- F⊆Q 是接受状态集(可以有多个接受状态s)
也就是说,以上几点唯一的确定一个有限自动机,自动机会有两个最终状态,接受或拒绝。
建立模型
好,开始建立模型:
- 首先,我们应该有一个用来描述有限自动机的对象,这个对象有接受输入,进行运算,得出结论等操作。当然,有限自动机也有很多种,确定型的和非确定型的,只要涉及到很多种具有共性的,我们一般会抽象出共性来做接口。
- 其次,我们可以看到,整个形式化定义都是基于集合的,我们应该有一个用以描述集合的对象,这个对象上可以进行添加元素,获取元素,删除元素,获取集合的大小等操作。
- 集合中是什么东西呢? 可以看到有状态,有字母表,我们可以考虑设计一个基类(元素),基类上可以拿到元素的真实值。
- 这个转移函数如何表示? δ实际上是一个矩阵,类似于数字电子中的真值表,因此我们需要有一个对象来表示这个转移函数,这个对象可以根据当前状态和输入字符来查出一个新的状态来(这就是它为什么叫转移函数的原因)。
抽象到这个粒度,可以看出整个系统中的所有对象我们都可以表示了,然后我们可以对这些对象进行适当的简化:
先看看自动机的接口:
/**
*
* @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();
}
集合的接口:
/**
*
* @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);
}
集合中元素的接口:
public interface Element {
/**
* get the real value of an element
* @return
*/
public String getValue();
}
转移函数:
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中是整个系统运行的脉络,如果接口定义的比较合理,清晰,那么代码读起来会很流畅,希望下面的代码读起来比较流畅,呵呵。
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. 本来要插入几张图片的,不知道为什么编辑到一半的时候插入图片老是插不进去,出来的对话框不知道怎么上传本地的图片。
发表评论
-
JavaScript内核系列 第15章 服务器端的JavaScript
2012-02-12 21:39 2210第15章已经在icodeit上发布,这一章分为上/下两篇,请朋 ... -
使用vim开发python及graphviz绘图
2011-12-23 14:49 6339基本需求 使用vim中的autocmd命令可以很容易的将正在 ... -
Java脚本技术应用实例
2011-01-22 11:24 4089前言 一直以来都很喜欢可以自由扩展的软件,这一点应该已经在很 ... -
可编程计算器(phoc)的设计与实现
2011-01-17 11:34 1862前言 借助JavaScript脚本 ... -
函数式编程(javascirpt)
2009-04-18 22:18 1216前言 Javascript,有人称 ... -
C和指针
2009-05-21 23:15 1058前言 指针是C的灵魂,正是指针使得C存在了这么多年,而且将长 ... -
C和指针(续)
2009-05-25 23:41 1312前言 上一篇《C和指针》可能对关于C和指针的有些内容没有说透 ... -
事件和监听器
2009-06-21 22:06 1364前言 事件监听器是经 ... -
基于总线的消息服务(BBMS)的设计与实现
2009-07-25 22:19 1309前言 异步事件的通知机制在比较有规模的软件设计中必然会有涉及 ... -
JavaScript内核系列 第9章 函数式的Javascript
2010-05-13 19:20 3707第九章 函数式的Javascript 要说Ja ... -
JavaScript内核系列 第8章 面向对象的JavaScript(下)
2010-05-06 09:40 3590接上篇:JavaScript内核系列 第8章 面向对象的Jav ... -
JavaScript内核系列 第8章 面向对象的JavaScript(上)
2010-05-06 09:26 2844第八章 面向对象的 Javascript ... -
JavaScript内核系列 第7章 闭包
2010-05-04 08:48 3772第七章 闭包 闭包向来给包括JavaScript程序 ... -
JavaScript内核系列 第6章 正则表达式
2010-04-27 19:44 3939第六章 正则表达式 正则表达式是对字符串的结构 ... -
JavaScript内核系列 第5章 数组
2010-04-24 15:17 4367第五章 数组 JavaScript的数组也是一个比较 ... -
Swing小应用(Todo-List)之三
2010-04-22 20:47 2065前言 去年9月份开发的那个小工具sTodo,只是做到了能用, ... -
JavaScript内核系列 第4章 函数
2010-04-18 17:31 4954第四章 函数 函数,在C语言之类的过程式语言中 ... -
JavaScript内核系列 第3章 对象与JSON
2010-04-12 09:12 6014第三章 对象与JSON JavaScript对象与传 ... -
JavaScript内核系列 第2章 基本概念
2010-04-03 19:44 5509第二章 基本概念 ... -
JavaScript内核系列 第1章 前言及概述
2010-04-01 23:15 9822前言 从2006年第一次接触JavaScript至今,算来也 ...
相关推荐
胞自动机是定义在网格上的,每一个点上的网格代表一个元胞与一种有限的状 态。变化规则适用于每一个元胞并且同时进行。典型的变化规则,决定于元胞的 状态,以及其(4 或 8 )邻居的状态。元胞自动机已被应用于物理...
具有半量子双向有限自动机建模的验证器的交互式证明系统的功能
元胞自动机(Cellular Automata),简称CA,也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循...
对于字符串数据类型,SE 工具通常使用有限状态自动机来表示符号字符串模型。因此,PSE 继承了基于 SE 自动机的符号字符串模型,以计算描述程序路径的基于字符串的约束的概率。然而,据我们所知,缺乏关于基于自动机...
方法基于“点点连格”机器博弈系统,利用 Moore自动机,为二人机器博弈系统建立了有限自动机模型,并在 Moor e自动机中引入受控子自动机,用监控器自动机作为该受控子自动机的输入控制器,实现了α-β搜索过程。...
一个农夫带着一只狼,一只羊和一筐菜,欲从河的左岸坐船到右岸,由于船太小,农夫每次只能带一样东西过河,并且没有农夫看管的话,狼会吃掉羊,羊会吃菜。设计一个方案,使农夫可以无损失的过河
在数学建模中,一般是借鉴元胞自动机的概念,应用于具体的适合于机理建模的问题中。这类问题的典型特征是,所研究的问题是一个系统问题,系统是由若干个一个或几个不同类的对象组成,经典的模型不适应。典型的问题如...
从机器鱼运动特点以及水环境的特点出发,以单鱼顶球算法为基础,以有限状态自动机的思路建模,对每条机器鱼的动作决策进行规划,从而能够高效地完成每条机器鱼的路径规划并避免互相干扰,以达到高效顶球的效果。...
您可以使用它来学习确定性系统的确定性有限自动机, Moore机器和Mealy机器。 如果您要学习的系统显示不确定性或随机行为,则AALpy允许您学习可观察的不确定性有限状态机,马尔可夫决策过程或随机换能器。 AALpy...
已经系统地提出了在FORTRAN上编程的二维元胞自动机(CA)方法与有限元(用于热建模)工具(CA-FE)结合的方法。 和在ABAQUS上并行模拟? 最能最有效地描述这种复杂的多物理场现象。 重点放在方法的
一个有限自动机的例子。假设一个自动贩卖机器可接受五分或者一角面值的钱币,卖15¢或20¢的单独包装的块状糖。假设这个贩卖机可以接受20¢,那么这个机器的状态图就可以由下图所示的Petri网来表示。五个状态用五个...
利用精确的数学模型描述其分布与并发行为:嵌入离散事件(DE)模型的有限自动机模型(FSM)描述软件模块内各进程间的并发及状态转换,定义基于层次图的双外推(DPO)变换建模系统拓扑结构的迁移。格件系统的描述表明...
其次,采用统计假设检验法与模型机理相结合的方法确定模型结构,然后,采用递推增广最小二乘法辨识模型参数,智能级监督模型参数的收敛性,最后,依据有限状态自动机的基本模型建立温度混杂自动机.采用实测数据进行仿真,...
把组合Web服务看成多智能体系统,将带有时间约束的Web服务智能体建模为时间自动机,通过并发组合构成时间自动机网络,从而用时间自动机验证工具UPPAAL对组合Web服务的运行过程进行模拟,并验证其活性、安全性和死锁等...
语法和语义层次的组合并不足以保证仿真组件组合的完整性、有效性和实用性,在语用组合问题分析的基础上,提出了基于扩展有限状态自动机的仿真组件模型形式化描述,包含了仿真组件行为语义和仿真运行语境约束信息,并...
元胞自动机由规则的单元格网格组成,每个单元格都处于有限状态中的一种,例如处于打开和关闭状态(与耦合的图格相反)。 网格可以是任意数量的尺寸。 对于每个单元,相对于指定单元定义了一组称为其邻域的单元。 ...
扩展DFA在动态流程框架中的建模应用,陈健荣,吕雪蕊,对基于扩展的确定有限状态机在动态流程框架中的业务建模应用进行了较全面的论述。首先对有限状态机的数学模型以及涉及框架进行介
把组合Web服务看成多智能体系统,将带有时间约束的Web服务智能体建模为时间自动机,通过并发组合构成时间自动机网络,从而用时间自动机验证工具UPPAAL对组合Web服务的运行过程进行模拟,并验证其活性、安全性和死锁...
针对操作系统测试需要,对Linux管道通信进行了源代码研究,使用有限状态自动机进行建模并转化为Promela语言,并运用SPIN模型检测工具对其进行了形式化验证;对之前研究中模型不完整、不够细化、主体间关联性等问题...
Autolife中的数字生命都可以看作自主决策的Agent, 它们用有限自动机建模; 同时程序允许Agent通过变异和繁殖而完成开放式的进化。在该模型的基础上, 本文主要针对Autolife涌现出来的数字生命个体行为、群体行为...