自动机编程

歷史

自動機編程的技術常用在以自動機原理為基礎的演算法中，例如形式語言分析。
詹森等在1968年發表的《Automatic generation of efficient lexical processors using finite state techniques》論文是早期提到自動機編程的論文。 Peter Naur在1963年的論文將自動機編程當成一種通用的軟體技術。作者將此技術稱為「圖靈機的方法」，不過此論文是以自動機的狀態及步驟為基礎，沒有提到圖靈機。

範例

考慮一個C語言的程式，由標準輸入流一行一行的讀取資料，列印各一行的第一個英文單字。因此一開始需確認第一個英文單字之前是否有空白，若有，需讀取所有空白後略過不列印，讀取第一個英文單字然後列印，之後讀取其他內容略過不列印，直到讀到換行符號為止。任何情形下只要讀到換行符號，就重新開始此演算法，任何情形下只要讀到檔案結束（end-of-file）的符號，就結束程式。

傳統C語言的程式

以下是傳統指令式編程的C語言程式：
#include <stdio.h>int main(void){
    int c;
    do {
        c = getchar();
        while(c == ' ')
            c = getchar();
        while(c != EOF && c != ' ' && c != '\n') {
            putchar(c);
            c = getchar();
        }
        putchar('\n');
        while(c != EOF && c != '\n')
            c = getchar();
    } while(c != EOF);
    return 0;}

自動機編程的程式

上述問題也可以用有有限狀態機的方式處理，此程式有三個不同的階段：讀取並跳過第一個單詞前的空白、讀取第一個單詞並且列印、跳過後續的所有字元。以下將這三個階段定義為三個狀態before、inside及after。自動機編程的程式如下：
#include <stdio.h>int main(void){
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        switch(state) {
            case before:
                if(c == '\n') {
                    putchar('\n');
                } else
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                switch(c) {
                    case ' ':  state = after; break;
                    case '\n':
                        putchar('\n');
                        state = before;
                        break;
                    default:   putchar(c);
                }
                break;
            case after:
                if(c == '\n') {
                    putchar('\n');
                    state = before;
                }
        }
    }
    return 0;}
雖然此程式較長，至少有一個明顯的好處，程式中只呼叫一個讀取字元的getchar()函式，而且程式中只有一個迴圈，不像之前程式使用四個迴圈。
此程式中while迴圈內的程式即為自動機的步驟，而迴圈本身即可重覆的執行自動機的程式。
此程式實現如右圖所示的有限狀態機，其中N表示換行字元、S表示空白、A表示其他的字元。自動機依目前狀態及讀取的字元不同，會執行圖中一個箭頭所示的動作，可能是由一個狀態跳到下一個狀態，也者停在原來的狀態。其中有些箭頭有標示星號，表示需列印讀到的字元。
自動機編程中，不一定要為每一個狀態撰寫獨立的處理程式，而且有時狀態是由許多變數組成，無法針對每一個狀態規劃個別的處理程式。此想法有時有助於程式的精簡，例如在上述程式中，不論是在哪一個狀態，針對換行字元的處理都一様，因此程式可以先處理換行字元，其他輸入字元時才依不同狀態進行處理，簡化後變成以下的程式：
#include <stdio.h>int main(void){
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        if(c == '\n') {
            putchar('\n');
            state = before;
        } else
        switch(state) {
            case before:
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                if(c == ' ') {
                    state = after;
                } else {
                    putchar(c);
                }
                break;
            case after:
                break;
        }
    }
    return 0;}

顯式的狀態轉換表

自動機編程可以用顯式的狀態轉換表來表示。以下的程式中的the_table陣列即為狀態轉換表，其列表示三個不同的狀態，其每一欄對應輸入的字元（從左到右分別是空白、換行字元及其他字元）。
對於每一種可能的狀態及輸入字元的組合，表中有其對應的新狀態及一個決定是否否顯示輸入字元的旗標。在實務的專案中狀態轉換表可能更為複雜，例如可能包括所有可能條件組合下需呼叫的函式指標。
#include <stdio.h>enum states { before = 0, inside = 1, after = 2 };struct branch {
    unsigned char new_state:2;
    unsigned char should_putchar:1;};struct branch the_table[3][3] = {
                 /* ' '         '\n'        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 == ' ') ? 0 : (c == '\n') ? 1 : 2;
    struct branch *b = & the_table[*state][idx2];
    *state = (enum states)(b->new_state);
    if(b->should_putchar) putchar(c);}int main(void){
    int c;
    enum states state = before;
    while((c = getchar()) != EOF)
        step(&state, c);
    return 0;}

自動化技術及事件

在自動化領域中，步驟之間的切換是依照機器本身的輸入資料，在本例中為讀到的輸入字元，在實務上可能是位置、速度、溫度等機器的關鍵資料。
自動化領域有些設計方式類似圖形化使用者介面的程式設計，機器狀態的改變可以視為由事件而造成，由於事件使機器由一個狀態變為下一個狀態，直到到達最後的狀態為止。可能出現狀態的組合可以產生許多的事件，因此可以定義較複雜的製造週期，其產生的製造週期一般會比線性循序流程複雜許多。一般常常會有一些同時執行的平行路徑，以及依不同事件決定執行方式的路徑，如下圖：

   s:狀態   c:條件
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   |        |
   |-c31    |-c32
   |        |
  s31       s32
   |        |
   |-c41    |-c42
   |        |
   ----------
   |
   s4

物件導向程式

若程式語言支援物件導向程式設計，就可以將自動機封裝為一個物件，隱藏自動機實現的細節。一種稱為「狀態模式」的設計模式即包括了此作法。上述的程式可以改為為以下的物件導向程式，利用C++來實現：
#include <stdio.h>class StateMachine {
    enum states { before = 0, inside = 1, after = 2 } state;
    struct branch {
        enum states new_state:2;
        int should_putchar:1;
    };
    static struct branch the_table[3][3];public:
    StateMachine() : state(before) {}
    void FeedChar(int c) {
        int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
        struct branch *b = & the_table[state][idx2];
        state = b->new_state;
        if(b->should_putchar) putchar(c);
    }};struct StateMachine::branch StateMachine::the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }};int main(void){
    int c;
    StateMachine machine;
    while((c = getchar()) != EOF)
        machine.FeedChar(c);
    return 0;}
註：為了減少和此主題不直接相關的修改，此處的輸入輸出函式使用C語言的標準函式庫，另外，其中的三元運算符?:也可以用if-else來實現。

應用

自動機編程常用在詞法分析及語法分析器中。
此外，用自動機的方式處理問題（將執行的程式分為自動機的步驟，以及各步驟間只透過顯式的狀態傳遞資訊）是事件驅動程式設計中必要的一部份，否則就要使用平行程式或是多執行緒的作法。
狀態及狀態機的表示法常用在形式規格的領域。例如以統一塑模語言為基礎的軟體架構開發，會使用狀態圖表示程式的行為，許多通訊協定也利用顯式的狀態來加以定義，例如RFC 793。
狀態機的思維也可以用來描述一些程式語言的語義，例如執行一個Refal語言的程式就可以描述為在抽象Refal機器上執行一連串的步驟，機器的狀態稱為view（任意的Refal表示式，其中沒有變數）。
Scheme程式語言不是一個和狀態機有關的程式語言（Scheme為遞迴式的），但其中的延續性（Continuation）需要以自動機的步驟及狀態的方式來思考。若要使call/cc的機能有效，需要可以記錄整個執行程式的狀態，只有在所有狀態都是顯式，不存在隱式狀態的情形下才可能達到。此處的「記錄完整狀態」即為延續性，可以視為一個較複雜自動機的狀態，自動機的步驟是由以前的延續性資料推斷下一個的延續性資料，而所執行的程式就是這些步驟的循環。
亞歷山大·奧隆格羅（Alexander Ollongren）在其著作中解釋了一種稱為「維也納方法」（Vienna method）的程式語言語義描述，完全以形式自動機為基礎。
UCSB的STAT（狀態轉移分析技術）系統是一個使用自動機編程的範例，此系統還包括一種稱為「STATL」的嵌入式語言，是完全自動機導向的語言。

和物件導向程式設計的關係

在物件導向程式設計的理論中，物件有其內部的狀態，而且可以接收訊息、回應訊息，傳送訊息給其他物件，且依訊息調整其內部的狀態。實際上，呼叫一個物件的方法也就是傳送訊息給此一物件。
因此，物件導向程式設計的物件也可以視為是自動機（或是自動機的模型），其狀態是內部屬性的組合，而物件的一個或多個方法可視為自動機的步驟。這些視為自動機步驟的方法不能直接或間接的互相呼叫（或呼叫本身），否則此物件就不能視為以自動機編程的方式來設計。
當用物件導向程式設計來實現自動機編程時，也可以用類別來實現自動機模型，其中狀態為其私有成員，而步驟是物件的一個公開方法，是除了建構子及解構子外，唯一可以變更物件內容的公開方法。物件的其他公開方法可以查詢狀態，但不能變更其狀態。物件的其他方法（例如不同狀態的處理程式）會是物件的私有方法，無法由外界程式來呼叫。