李峰松，婁淵勝

(河海大學，南京 210000)

本文從有限自動機的理論出發(fā)，詳細介紹了自動機的理論知識，包括確定的有限自動機和不確定的有限自動機[1-4].把有限自動機的五元組理論應用于聲光報警器的設計.[5]

所設計的報警器是簡單的聲光報警器，包含三個傳感器：煙幕傳感器、煙幕傳感器、聲音采集模塊，這三個傳感器主要用于探測火災或小偷進入，對一般家庭的防范還是起到很好的作用.處理器用的是單片機AT89C51.

1 有限自動機理論

1.1 有限自動機的基本原理

自動機通過接受一定的輸入，執(zhí)行一定的動作后，產(chǎn)生一定的結果.可以用狀態(tài)遷移描述整個過程.自動機的本質：根據(jù)狀態(tài)、輸入、規(guī)則決定下一個狀態(tài).即狀態(tài)+輸入(激勵)+規(guī)則-->狀態(tài)遷移.如圖1所示為有限自動機示意圖每個有限自動機由3部分組成：一個有限控制器、一個讀頭、一個寫有字符的輸入帶.它的工作原理為：讀頭在輸入帶上從左向右移動，每當讀頭從帶上讀到一個字符時，便引起控制器狀態(tài)的改變，同時讀頭右移一個符號的位置.控制器包括有限個狀態(tài)，狀態(tài)與狀態(tài)之間存在著某種轉換關系.每當在某一狀態(tài)下讀入一個字符時，便使狀態(tài)發(fā)生改變(稱為狀態(tài)轉換)[6-7].

圖1 有限自動機示意圖

狀態(tài)轉換包括以下幾種情況：1) 轉換到其自身，即保持當前狀態(tài)不變2)轉換的后繼狀態(tài)只有一個3) 轉換的后繼狀態(tài)有若干個.

如果一個有限自動機每次轉換的后繼狀態(tài)都是唯一的，稱為確定的有限自動機(DFA)；如果轉換的后繼狀態(tài)不是惟一的，則稱為不確定的有限自動機(NFA).

通常把有限自動機開始工作的狀態(tài)稱為“初始狀態(tài)”，把結束工作的狀態(tài)稱為“終止狀態(tài)”或“接受狀態(tài)”[8-10].

1.2 確定的有限自動機(DFA)

確定的有限自動機是一個五元組M=(Q,∑,δ,q0，F(xiàn))其中：Q為狀態(tài)的非空有窮集合.?q∈Q，q稱為M的一個狀態(tài).∑為輸入字母表.輸入字符串都是∑上的字符串.δ為狀態(tài)轉移函數(shù).δ為Q×M→Q，對?(q,a)∈Q×∑，δ(q,a)=p表示M在狀態(tài)q讀入字符a，將狀態(tài)變成p,并將讀頭向右移動一個方格而指向輸入字符串的下一個字符.q0：q0∈Q，是M的開始狀態(tài)，也可以叫做初始狀態(tài)或啟動狀態(tài).F為F?Q，是M的終止狀態(tài)集合.

1.3 不確定的有限自動機(NFA)

不確定的有限自動機是一個五元組M=(Q,∑,δ,q0，F(xiàn)).其中：Q,∑，q0，F(xiàn)的意義同DNF.

δ為Q×Σ→2Q，對?(q，a)∈Q×Σ，δ(q，a)= {p1，p2，…，pm}表示M在狀態(tài)q讀入字符a，可以選擇地將狀態(tài)變成p1、或者p2、…、或者pm，并將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符.

DFA與NFA的區(qū)別：1)NFA允許多個初始狀態(tài).2)同一輸入字符可以有多個后繼狀態(tài).

2 家用防火防盜有限自動機的設計

2.1 基于有限自動機理論的報警器分析

通過對家用防火防盜報警器的整體功能分析，將報警器的整個運行過程作為一個有窮自動機，記為M=(Q,∑,δ,q0，F(xiàn)).

1) 將報警器在其整個運行周期中可能的狀態(tài)作為狀態(tài)集Q(括號中的字母為其代號).Q={“開關開啟(q0)”，“傳感器等待狀態(tài)(q1)”，“紅外傳感器觸發(fā)狀態(tài)(q2)”，“聲音采集傳感器觸發(fā)狀態(tài)(q3)”，“煙幕傳感器觸發(fā)狀態(tài)(q4)”，“報警燈閃爍狀態(tài)(q5)”，“蜂鳴器響應狀態(tài)(q6)”，“關閉狀態(tài)(q7)” }.

2) 將觸發(fā)報警的激勵源作為M的輸入字母表Σ(括號中的字母為該激勵源的代號).

Σ={復位操作(a),紅外線發(fā)出(b),聲音產(chǎn)生(c)，煙幕產(chǎn)生(d),單片機處理信息后送出低電平(e),單片機處理信息后送出高電平(f),關閉開關操作(g)}.

3) 將“開關開啟”作為設備開始狀態(tài)即q0=“開關開啟”.

4) 將“關閉狀態(tài)”作為M的終止狀態(tài)集.即F={“關閉狀態(tài)”}.

5) 將各種動作對報警器所引起的狀態(tài)變化作為M的從Q×M→Q的映射δ(δ描述中，引起狀態(tài)變化的動作用相應的字母代號表示)，δ定義如下：

δ(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

其相應的狀態(tài)轉換圖如圖2所示.

圖2 狀態(tài)轉換圖

2.2 報警器的整體模塊及工作流圖分析

家用防盜防火報警器整體硬件結構包括：復位電路、煙幕傳感器模塊、聲音采集模塊、熱釋紅外傳感器模塊，單片機AT89C51、驅動電路、LED報警燈、蜂鳴器.其整體結構如圖3所示.其工作流程見圖4.

圖3 報警器整體結構

圖4 報警器工作流程圖

3 結 語

本文用有限自動機理論詳細分析了家用防盜防火報警器的運行過程，從狀態(tài)轉移圖可以分析所設計報警器的工作原理.按有限自動機思想設計的報警器能夠達到較好的實用效果.

參考文獻：

[1] 胡海編. 單片機原理與應用[M]. 北京：機械工業(yè)出版社，2005.

[2] 黃繼昌. 傳感器工作原理及應用實例[M]. 北京: 人民郵電出版社, 1998.

[3] 張慶雙. 報警器、警示器應用電路集粹[M]. 北京: 北京機械工業(yè)出版社, 2005.

[4] 王 偉, 黃俊恒, 徐永東. 有窮自動機在車輛管理系統(tǒng)開發(fā)中的應用[J]. 哈爾濱商業(yè)大學學報：自然科學版, 2012, 28(4): 444-446.

[5] 習仲堅, 巫 明. 有窮自動機理論在自動化控制方面的應用[J]. 自動化儀器與儀表, 2012, 6: 105-108.

[6] 羅光春, 李 炯. 有限自動機在BBS信息監(jiān)測系統(tǒng)中的應用[J]. 電子科學大學學報, 2002, 31(3): 262-265.

[7] 盧良進. 基于形式語言的計算機自動閱卷機制研究[J]. 軟件導刊, 2010, 9(10): 104-106.

[8] 蔣宗禮, 姜守旭. 形式語言與自動機理論[M]. 北京: 清華大學出版社, 2003.

[9] HOPCROFT J E, MOTWANI R, ULLMAN J D. Introduction to Automata Theory, Languages, and Computation [J]. ACM SIGACT News, 1979, 32(1): 60-65.

[10] 王 偉，黃俊恒，徐永東.有窮自動機在車輛管理系統(tǒng)開發(fā)中的應用[J]. 哈爾濱商業(yè)大學學報：自然科學版，2012，28(4)：444-446.