有限自動機在自動柜員機測控程序設計中的應用

摘要：本文介紹了有限自動機的概念，形式化定義及基本組成，通過舉例闡述了有限自動機在自動柜員機上的應用。

關鍵詞：有限自動機 自動柜員機 狀態轉換

0 引言

有限自動機是一種研究離散事件動態系統的數學模型，它出現于20世紀40年代，1943年麥克卡賽(McCulloch)與皮特斯(Pitts)建立了模擬神經網絡的自動機。1956年莫爾(Moore)建立了描述計算機的時序機的概念。此后，自動機理論迅速發展，與計算機技術密切結合，在人工智能、自動控制等領域有廣泛應用。

有限自動機是計算機科學的重要基石，它可以用來研究時序線路與計算機的構造，是計算機硬件的理論基礎。由于計算機中的數以二進制形式表示，所以計算機基本的加法器功能可以用有限自動機來實現。計算機的操作系統在信息處理進程中需要一定資源。在不同資源條件下，進程處于不同的狀態。進程活動中要不斷提出申請資源和歸還資源的請求，這些請求與進程的狀態和資源的條件有關。操作系統的這些活動體現了一個有限自動機的功能特征，因此操作系統的信息處理過程可以用有限自動機來刻畫。

1 有限自動機的形式描述

SW有限自動機(DFA)是一個五元組：M=(Q，T，δ，q0，F)。其中：

Q：有限的狀態集合；

T：有限的輸入字母表；

δ：轉換函數，是從Ｑ×Ｔ到Ｑ的映射；

q0：初始狀態。

F：終止狀態集，F Q。

轉換函數δ是用來表示狀態轉換關系的，對狀態q，p∈Q，字符a∈T，當在狀態q，讀入字符或是輸入字符a后，狀態換成p，用轉換函數表示，則是δ（q，a）=p。

當有限自動機讀入一個字符串時，它從初始狀態q0開始，經過一系列狀態的轉換，最后如果能夠到達終止狀態，則稱這一字符串可被有限自動機接受，否則，該字符串不被接受。

2 有限自動機在自動柜員機測控程序設計中的應用

ATM工作主要流程，首先，插入磁卡并且選擇語言，然后輸入密碼（一天最多3次機會）。然后，選擇服務類型，取款或是存款，最后，成功后，可以選擇退出服務，也可以繼續選擇服務類型。具體工作流程如圖1所示：

應用有限自動機(FA)理論對狀態轉換圖進行分析如下:

這樣“a”表示前進過程操作成功；“b”狀態不變，即密碼輸入不正確時，重新輸入密碼；“c”表示返回操作成功，即存款后我們可以返回再取款，或是取款后我們返回再存款，而不必完成操作退卡后，再重新插入卡重復操作，那樣操作就太繁瑣了；“d”表示密碼三次輸入不對，直接完成操作，退卡。“q0”、“q1”、“q2”不變，此時的“q3”表示存款/取款，此時的“q4”表示終止狀態。

3 結語

在客觀實際中，很多過程雖然有不同的表象，但他們的內部運行規律是相同的，所以可以用相同的有限自動機表示。因此，我們給出一個有限自動機模型，就描述了客觀實際中一類具有相同的運行機制的裝置或過程。這一事實決定了利用有限自動機所開發的實用測控程序會具有很好的通用性和可移植性。

參考文獻：

[1]陳崇聽.形式語言與自動機[M].北京：北京郵電學院出版社，1988.11.

[2]鄭大鐘.離散事件動態系統[M].北京：清華大學出版社，2001.

[3]黃志強，蘇穎.有限自動機在自動控制軟件設計中的應用[J].華北電力大學學報，2002，1.

[4]Kenneth H Rosen1 Discrete mathematics and its applications[M].McGraw hill.1998.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文