有限自动机与建模

有限自动机与建模2011-09-30 博客园 abruzzi前言

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

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

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

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

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

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

有限自动机

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

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

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

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

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

q0∈Q 是其实状态

F⊆Q 是接受状态集（可以有多个接受状态s）

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