有限自动机在家用防火防盗报警器中的应用

2014-09-14李峰松娄渊胜

哈尔滨商业大学学报（自然科学版） 2014年6期

关键词：烟幕后继自动机

李峰松，娄渊胜

(河海大学，南京 210000)

本文从有限自动机的理论出发，详细介绍了自动机的理论知识，包括确定的有限自动机和不确定的有限自动机[1-4].把有限自动机的五元组理论应用于声光报警器的设计.[5]

所设计的报警器是简单的声光报警器，包含三个传感器：烟幕传感器、烟幕传感器、声音采集模块，这三个传感器主要用于探测火灾或小偷进入，对一般家庭的防范还是起到很好的作用.处理器用的是单片机AT89C51.

1 有限自动机理论

1.1 有限自动机的基本原理

自动机通过接受一定的输入，执行一定的动作后，产生一定的结果.可以用状态迁移描述整个过程.自动机的本质：根据状态、输入、规则决定下一个状态.即状态+输入(激励)+规则-->状态迁移.如图1所示为有限自动机示意图每个有限自动机由3部分组成：一个有限控制器、一个读头、一个写有字符的输入带.它的工作原理为：读头在输入带上从左向右移动，每当读头从带上读到一个字符时，便引起控制器状态的改变，同时读头右移一个符号的位置.控制器包括有限个状态，状态与状态之间存在着某种转换关系.每当在某一状态下读入一个字符时，便使状态发生改变(称为状态转换)[6-7].

图1 有限自动机示意图

状态转换包括以下几种情况：1) 转换到其自身，即保持当前状态不变2)转换的后继状态只有一个3) 转换的后继状态有若干个.

如果一个有限自动机每次转换的后继状态都是唯一的，称为确定的有限自动机(DFA)；如果转换的后继状态不是惟一的，则称为不确定的有限自动机(NFA).

通常把有限自动机开始工作的状态称为“初始状态”，把结束工作的状态称为“终止状态”或“接受状态”[8-10].

1.2 确定的有限自动机(DFA)

确定的有限自动机是一个五元组M=(Q,∑,δ,q0，F)其中：Q为状态的非空有穷集合.∀q∈Q，q称为M的一个状态.∑为输入字母表.输入字符串都是∑上的字符串.δ为状态转移函数.δ为Q×M→Q，对∀(q,a)∈Q×∑，δ(q,a)=p表示M在状态q读入字符a，将状态变成p,并将读头向右移动一个方格而指向输入字符串的下一个字符.q0：q0∈Q，是M的开始状态，也可以叫做初始状态或启动状态.F为F⊆Q，是M的终止状态集合.

1.3 不确定的有限自动机(NFA)

不确定的有限自动机是一个五元组M=(Q,∑,δ,q0，F).其中：Q,∑，q0，F的意义同DNF.

δ为Q×Σ→2Q，对∀(q，a)∈Q×Σ，δ(q，a)= {p1，p2，…，pm}表示M在状态q读入字符a，可以选择地将状态变成p1、或者p2、…、或者pm，并将读头向右移动一个带方格而指向输入字符串的下一个字符.

DFA与NFA的区别：1)NFA允许多个初始状态.2)同一输入字符可以有多个后继状态.

2 家用防火防盗有限自动机的设计

2.1 基于有限自动机理论的报警器分析

通过对家用防火防盗报警器的整体功能分析，将报警器的整个运行过程作为一个有穷自动机，记为M=(Q,∑,δ,q0，F).

1) 将报警器在其整个运行周期中可能的状态作为状态集Q(括号中的字母为其代号).Q={“开关开启(q0)”，“传感器等待状态(q1)”，“红外传感器触发状态(q2)”，“声音采集传感器触发状态(q3)”，“烟幕传感器触发状态(q4)”，“报警灯闪烁状态(q5)”，“蜂鸣器响应状态(q6)”，“关闭状态(q7)” }.

2) 将触发报警的激励源作为M的输入字母表Σ(括号中的字母为该激励源的代号).

Σ={复位操作(a),红外线发出(b),声音产生(c)，烟幕产生(d),单片机处理信息后送出低电平(e),单片机处理信息后送出高电平(f),关闭开关操作(g)}.

3) 将“开关开启”作为设备开始状态即q0=“开关开启”.

4) 将“关闭状态”作为M的终止状态集.即F={“关闭状态”}.

5) 将各种动作对报警器所引起的状态变化作为M的从Q×M→Q的映射δ(δ描述中，引起状态变化的动作用相应的字母代号表示)，δ定义如下：

δ(q0，a)=q1，δ(q1，b)=q2

δ(q1，c)=q3,δ(q1，d)=q4

δ(q2，e)=q6,δ(q2，f)=q7

δ(q3，e)=q6,δ(q3，f)=q7

δ(q4，e)=q5,δ(q4，f)=q6

δ(q5，g)=q7,δ(q6，f)=q7

其相应的状态转换图如图2所示.