自動(dòng)機(jī)編程

自動(dòng)機(jī)編程的技術(shù)常用在以自動(dòng)機(jī)原理為基礎(chǔ)的算法中，例如形式語言分析[1]。

約翰遜等在1968年發(fā)表的《Automatic generation of efficient lexical processors using finite state techniques》論文是早期提到自動(dòng)機(jī)編程的論文[2]。 Peter Naur在1963年的論文將自動(dòng)機(jī)編程當(dāng)成一種通用的軟件技術(shù)[3]。作者將此技術(shù)稱為“圖靈機(jī)的方法”，不過此論文是以自動(dòng)機(jī)的狀態(tài)及步驟為基礎(chǔ)，沒有提到圖靈機(jī)。

考慮一個(gè)C語言的程式，由標(biāo)準(zhǔn)輸入流一行一行的讀取資料，打印各一行的第一個(gè)英文單字。因此一開始需確認(rèn)第一個(gè)英文單字之前是否有空白，若有，需讀取所有空白后略過不打印，讀取第一個(gè)英文單字然后打印，之后讀取其他內(nèi)容略過不打印，直到讀到換行符號(hào)為止。任何情形下只要讀到換行符號(hào)，就重新開始此算法，任何情形下只要讀到檔案結(jié)束（end-of-file）的符號(hào)，就結(jié)束程式。

傳統(tǒng)C語言的程式

以下是傳統(tǒng)指令式編程的C語言程式：

#include int main(void)

{int c;

do

{

c =getchar();

while(c ==' ') c =getchar();

while(c != EOF && c !=' '&& c !=' ')

{

putchar(c); c =getchar();}putchar(' ');

while(c != EOF && c !=' ') c =getchar();

}

while(c != EOF);return0;}

自動(dòng)機(jī)編程的程式

上述問題也可以用有有限狀態(tài)機(jī)的方式處理，此程式有三個(gè)不同的階段：讀取并跳過第一個(gè)單字前的空白、讀取第一個(gè)單字并且打印、跳過后續(xù)的所有字符。以下將這三個(gè)階段定義為三個(gè)狀態(tài)before、inside及after。自動(dòng)機(jī)編程的程式如下：

#include int main(void){enum states { before, inside, after } state;int c;、 state = before;while((c =getchar())!= EOF){switch(state){case before:if(c ==' '){putchar(' ');}elseif(c !=' '){putchar(c); state = inside;}break;case inside:switch(c){case' ': state = after;break;case' ':putchar(' '); state = before;break;default:putchar(c);}break;case after:if(c ==' '){putchar(' '); state = before;}}}return0;}

雖然此程式較長，至少有一個(gè)明顯的好處，程式中只呼叫一個(gè)讀取字符的getchar()函數(shù)，而且程式中只有一個(gè)循環(huán)，不像之前程式使用四個(gè)循環(huán)。

此程式中while循環(huán)內(nèi)的程式即為自動(dòng)機(jī)的步驟，而循環(huán)本身即可重復(fù)的執(zhí)行自動(dòng)機(jī)的程序。

此程式實(shí)現(xiàn)有限狀態(tài)機(jī)，其中 N表示換行字符、 S表示空白、 A表示其他的字符。自動(dòng)機(jī)依狀態(tài)及讀取的字符不同，會(huì)執(zhí)行一個(gè)箭頭所示的動(dòng)作，可能是由一個(gè)狀態(tài)跳到下一個(gè)狀態(tài)，也者停在原來的狀態(tài)。其中有些箭頭有標(biāo)示星號(hào)，表示需打印讀到的字符。

自動(dòng)機(jī)編程中，不一定要為每一個(gè)狀態(tài)撰寫?yīng)毩⒌奶幚沓绦颍矣袝r(shí)狀態(tài)是由許多變量組成，無法針對(duì)每一個(gè)狀態(tài)規(guī)劃個(gè)別的處理程序。此想法有時(shí)有助于程式的精簡(jiǎn)，例如在上述程式中，不論是在哪一個(gè)狀態(tài)，針對(duì)換行字符的處理都一様，因此程式可以先處理換行字符，其他輸入字符時(shí)才依不同狀態(tài)進(jìn)行處理，簡(jiǎn)化后變成以下的程式：

#include int main(void){enum states { before, inside, after } state;int c; state = before;while((c =getchar())!= EOF){if(c ==' '){putchar(' '); state = before;}elseswitch(state){case before:if(c !=' '){putchar(c); state = inside;}break;case inside:if(c ==' '){ state = after;}else{putchar(c);}break;case after:break;}}return0;}

獨(dú)立的自動(dòng)機(jī)步驟程式

上述程式的一個(gè)重要特點(diǎn)是自動(dòng)機(jī)步驟的程式區(qū)塊都只使用區(qū)域變量，以下的例子將自動(dòng)機(jī)步驟整合為一個(gè)獨(dú)立的函式step()，更可以突顯上述的特點(diǎn)：

#include enum states { before, inside, after };void step(enum states *state,int c){if(c ==' '){putchar(' ');*state = before;}elseswitch(*state){case before:if(c !=' '){putchar(c);*state = inside;}break;case inside:if(c ==' '){*state = after;}else{putchar(c);}break;case after:break;}}int main(void){int c;enum states state = before;while((c =getchar())!= EOF){ step(&state, c);}return0;}

此例清楚的呈現(xiàn)自動(dòng)機(jī)編程程式的基本特點(diǎn)：

各自動(dòng)機(jī)步驟程式的執(zhí)行時(shí)間不互相重疊。

前一個(gè)步驟和下一個(gè)步驟之間所交換的資料只有標(biāo)示為“自動(dòng)機(jī)狀態(tài)”的變量（此例中為變量state）。

顯式的狀態(tài)轉(zhuǎn)換表

自動(dòng)機(jī)編程可以用顯式的狀態(tài)轉(zhuǎn)換表來表示。以下的程式中的the_table陣列即為狀態(tài)轉(zhuǎn)換表，其列表示三個(gè)不同的狀態(tài)，其每一欄對(duì)應(yīng)輸入的字符（從左到右分別是空白、換行字符及其他字符）。

對(duì)于每一種可能的狀態(tài)及輸入字符的組合，表中有其對(duì)應(yīng)的新狀態(tài)及一個(gè)決定是否否顯示輸入字符的旗標(biāo)。在實(shí)務(wù)的專案中狀態(tài)轉(zhuǎn)換表可能更為復(fù)雜，例如可能包括所有可能條件組合下需呼叫的函式指標(biāo)。

#include enum states { before =0, inside =1, after =2};struct branch {unsignedchar new_state:2;unsignedchar should_putchar:1;};struct branch the_table[3][3]={/* ' ' ' ' others *//* before */{{before,0},{before,1},{inside,1}},/* inside */{{after,0},{before,1},{inside,1}},/* after */{{after,0},{before,1},{after,0}}};void step(enum states *state,int c){int idx2 =(c ==' ')"para" label-module="para">

自動(dòng)化技術(shù)和自動(dòng)機(jī)

自動(dòng)機(jī)編程相當(dāng)類似自動(dòng)化技術(shù)領(lǐng)域需要的程式。

制造周期一般會(huì)用以下的方式定義：

一串依輸入資料決定狀態(tài)的程序。

依狀態(tài)輸出對(duì)應(yīng)資料的程序。

許多編程語言可以用類似的方式撰寫程式。

上述程式可以用此觀點(diǎn)改寫，以下是改寫后程式的虛擬碼，其使用關(guān)鍵字和符號(hào)說明如下：

'set'是指設(shè)定變量（此處為狀態(tài)）的數(shù)值

':'為設(shè)定變量，'='是判斷是否相等

SPC :' 'EOL :' ' states :(before, inside, after, end) setState(c){if c=EOF then set end if before and (c!=SPC and c!=EOL) then set inside if inside and (c=SPC or c=EOL) then set after if after and c=EOL then set before} doAction(c){if inside then write(c)elseif c=EOL then write(c)} cycle { set before loop { c : readCharacter setState(c) doAction(c)} until end}

上述程式中將更新狀態(tài)的程式獨(dú)立為setState函式，另外將依狀態(tài)和輸入更新輸出的程式獨(dú)立為doAction函式，此作法可以產(chǎn)生較清楚及簡(jiǎn)單的程式碼。

[編輯]自動(dòng)化技術(shù)及事件在自動(dòng)化領(lǐng)域中，步驟之間的切換是依照機(jī)器本身的輸入資料，在本例中為讀到的輸入字符，在實(shí)務(wù)上可能是位置、速度、溫度等機(jī)器的關(guān)鍵資料。

自動(dòng)化領(lǐng)域有些設(shè)計(jì)方式類似圖形用戶界面的程式設(shè)計(jì)，機(jī)器狀態(tài)的改變可以視為由事件而造成，由于事件使機(jī)器由一個(gè)狀態(tài)變?yōu)橄乱粋€(gè)狀態(tài)，直到到達(dá)最后的狀態(tài)為止?？赡艹霈F(xiàn)狀態(tài)的組合可以產(chǎn)生許多的事件，因此可以定義較復(fù)雜的制造周期，其產(chǎn)生的制造周期一般會(huì)比線性循序流程復(fù)雜許多。一般常常會(huì)有一些同時(shí)執(zhí)行的平行路徑，以及依不同事件決定執(zhí)行方式的路徑。

s:狀態(tài) c:條件 s1 | |-c2 | s2 | ---------- | | |-c31 |-c32 | | s31 s32 | | |-c41 |-c42 | | ---------- | s4

面向?qū)ο蟪淌?

若編程語言支援面向?qū)ο蟪淌皆O(shè)計(jì)，就可以將自動(dòng)機(jī)封裝為一個(gè)物件，隱藏自動(dòng)機(jī)實(shí)現(xiàn)的細(xì)節(jié)。一種稱為“狀態(tài)模式（英語：State pattern）”的設(shè)計(jì)模式即包括了此作法。上述的程式可以改為為以下的面向?qū)ο蟪淌?，利用C 來實(shí)現(xiàn)：

#include class StateMachine {enum states { before =0, inside =1, after =2} state;struct branch {enum states new_state:2;int should_putchar:1;};staticstruct branch the_table[3][3];public: StateMachine(): state(before){}void FeedChar(int c){int idx2 =(c ==' ')"para" label-module="para">

注：為了減少和此主題不直接相關(guān)的修改，此處的輸入輸出函數(shù)使用C語言的標(biāo)準(zhǔn)函式庫，另外，其中的三元運(yùn)算符

自動(dòng)機(jī)編程有以下的二項(xiàng)特征：

程式執(zhí)行的時(shí)間中可以清楚劃分成數(shù)個(gè)自動(dòng)機(jī)的步驟（step），每一個(gè)步驟即為一個(gè)程式區(qū)段，有單一的進(jìn)入點(diǎn)，可以是一個(gè)函數(shù)或其他程序。若有需要時(shí)，程式區(qū)段可以再依其狀態(tài)的不同，劃分為子區(qū)段。

不同步驟的程式區(qū)段只能透過一組清楚標(biāo)示的變量交換資訊，這些變量稱為狀態(tài)（state），使用自動(dòng)機(jī)編程的程式不能用其他不顯然可見的方式標(biāo)示狀態(tài)，例如區(qū)域變量的數(shù)值、回傳位址、程式指標(biāo)的位置等。因此一程式在任二個(gè)不同時(shí)間下的差異，只有狀態(tài)數(shù)值的不同，其余都相同。

自動(dòng)機(jī)編程的執(zhí)行過程是一個(gè)由自動(dòng)機(jī)步驟形成的循環(huán)。

自動(dòng)機(jī)編程中處理問題的思考方式很類似在利用圖靈機(jī)、馬爾可夫算法處理問題時(shí)的思考方式。

上述自動(dòng)機(jī)接受的語言家族被稱為正規(guī)語言(Regular Expression)。更強(qiáng)力的自動(dòng)機(jī)可以接受更復(fù)雜的語言。比如:

自動(dòng)機(jī)PDA

PDA(下推自動(dòng)機(jī))這種機(jī)器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內(nèi)存。轉(zhuǎn)移函數(shù) δ 也依賴于在棧頂?shù)姆?hào)，并在每次轉(zhuǎn)移時(shí)指定如何變更棧。非確定 PDA 接受上下文無關(guān)語言。

自動(dòng)機(jī)LBA

LBA （線性有界自動(dòng)機(jī)）是有限制的 圖靈機(jī)；不使用無限磁帶，它的磁帶有同輸入字元串成正比的空間。LBA 接受上下文有關(guān)語言。

自動(dòng)機(jī)圖靈機(jī)

它們是最強(qiáng)力的電腦器。它們擁有磁帶形式的無限內(nèi)存，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動(dòng)。圖靈機(jī)等價(jià)于演算法，是現(xiàn)代電腦的理論基礎(chǔ)。圖靈機(jī)判定遞歸語言并識(shí)別遞歸可枚舉語言。

下面是三類有限自動(dòng)機(jī)

確定有限自動(dòng)機(jī)(DFA)

自動(dòng)機(jī)的每個(gè)狀態(tài)都有對(duì)字母表中所有符號(hào)的轉(zhuǎn)移。

非確定有限自動(dòng)機(jī)(NFA)

自動(dòng)機(jī)的狀態(tài)對(duì)字母表中的每個(gè)符號(hào)可以有也可以沒有轉(zhuǎn)移，對(duì)一個(gè)符號(hào)甚至可以有多個(gè)轉(zhuǎn)移。自動(dòng)機(jī)接受一個(gè)字，如果存在至少一個(gè)從 q0 到 F 中標(biāo)記(label)著這個(gè)輸入字的一個(gè)狀態(tài)的路徑。如果一個(gè)轉(zhuǎn)移是「未定義」的，自動(dòng)機(jī)因此不知道如何繼續(xù)讀取輸入，則拒絕這個(gè)字。

有ε轉(zhuǎn)移的非確定有限自動(dòng)機(jī)(FND-ε或ε-NFA)

除了有能力對(duì)任何符號(hào)跳轉(zhuǎn)到更多狀態(tài)或沒有狀態(tài)可以跳轉(zhuǎn)之外，它們可以做根本不關(guān)于符號(hào)的跳轉(zhuǎn)。就是說，如果一個(gè)狀態(tài)有標(biāo)記著 ε 的轉(zhuǎn)移，則 NFA 可以處在 ε-轉(zhuǎn)移可到達(dá)的任何狀態(tài)中，直接或通過其他有 ε-轉(zhuǎn)移的狀態(tài)。從一個(gè)狀態(tài) q 通過這種方法可到達(dá)的狀態(tài)的集合叫做 q 的 ε-閉包。

盡管可以證明所有這些自動(dòng)機(jī)都「可以接受同樣的語言」。你總是可以構(gòu)造接受與給定的 NFA M 同樣語言的某個(gè) DFA M。

自動(dòng)機(jī)是有限狀態(tài)機(jī)(FSM)的數(shù)學(xué)模型。

FSM 是給定符號(hào)輸入，依據(jù)(可表達(dá)為一個(gè)表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過一系列狀態(tài)的一種機(jī)器。在常見的 FSM 的“Mealy”變體中，這個(gè)轉(zhuǎn)移函數(shù)告訴自動(dòng)機(jī)給定當(dāng)前狀態(tài)和當(dāng)前字符的時(shí)候下一個(gè)狀態(tài)是什么。

逐個(gè)讀取輸入中的符號(hào)，直到被完全耗盡(把它當(dāng)作有一個(gè)字寫在其上的磁帶，通過自動(dòng)機(jī)的讀磁頭來讀取它；磁頭在磁帶上前行移動(dòng)，一次讀一個(gè)符號(hào))。一旦輸入被耗盡，自動(dòng)機(jī)被稱為“停止”了。

依賴自動(dòng)機(jī)停止時(shí)的狀態(tài)，稱呼這個(gè)自動(dòng)機(jī)要么是“接受”要么“拒絕”這個(gè)輸入。如果停止于“接受狀態(tài)”，則自動(dòng)機(jī)“接受”了這個(gè)字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個(gè)字被“拒絕”。自動(dòng)機(jī)接受的所有字的集合被稱為“這個(gè)自動(dòng)機(jī)接受的語言”。

自動(dòng)機(jī) automaton 原來是模仿人和動(dòng)物的行動(dòng)而做成的機(jī)器人的意思。但是現(xiàn)已被抽象化為如下的機(jī)器。時(shí)間是離散的（t=0，1，2……），在每一個(gè)時(shí)刻它處于所存在的有限個(gè)內(nèi)部狀態(tài)中的一個(gè)。對(duì)每一個(gè)時(shí)刻給予有限個(gè)輸入中的一個(gè)。那么下一個(gè)時(shí)刻的內(nèi)部狀態(tài)就由現(xiàn)在的輸入和現(xiàn)在的內(nèi)部狀態(tài)所決定。每個(gè)時(shí)刻的輸出只由那個(gè)時(shí)刻的內(nèi)部狀態(tài)所決定。作為自動(dòng)機(jī)的例子可以舉出由McCulloch-pitts的神經(jīng)模型組合所得到的神經(jīng)網(wǎng)絡(luò)模型、數(shù)字計(jì)算機(jī)等。