自動機編程特征

自動機編程有以下的二項特征：

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

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

自動機編程的執(zhí)行過程是一個由自動機步驟形成的循環(huán)。

自動機編程中處理問題的思考方式很類似在利用圖靈機、馬爾可夫算法處理問題時的思考方式。

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

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

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

自動機編程的程式

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

#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;}

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

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

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

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

#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;}

獨立的自動機步驟程式

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

#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)自動機編程程式的基本特點：

各自動機步驟程式的執(zhí)行時間不互相重疊。

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

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

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

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

#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">

自動化技術(shù)和自動機

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

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

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

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

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

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

'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)的程式獨立為setState函式，另外將依狀態(tài)和輸入更新輸出的程式獨立為doAction函式，此作法可以產(chǎn)生較清楚及簡單的程式碼。

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

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

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

面向?qū)ο蟪淌?

若編程語言支援面向?qū)ο蟪淌皆O(shè)計，就可以將自動機封裝為一個物件，隱藏自動機實現(xiàn)的細節(jié)。一種稱為“狀態(tài)模式（英語：State pattern）”的設(shè)計模式即包括了此作法。上述的程式可以改為為以下的面向?qū)ο蟪淌剑肅 來實現(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語言的標準函式庫，另外，其中的三元運算符

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

自動機PDA

PDA(下推自動機)這種機器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內(nèi)存。轉(zhuǎn)移函數(shù) δ 也依賴于在棧頂?shù)姆枺⒃诿看无D(zhuǎn)移時指定如何變更棧。非確定 PDA 接受上下文無關(guān)語言。

自動機LBA

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

自動機圖靈機

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

下面是三類有限自動機

確定有限自動機(DFA)

自動機的每個狀態(tài)都有對字母表中所有符號的轉(zhuǎn)移。

非確定有限自動機(NFA)

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

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

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

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

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

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

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

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

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