沒有記憶的機器

雖然磁帶、堆疊只是存取資料用的設備，然而，能將運算的結果暫時以某種方式儲存下來，機器就有能力先去執行其他運算，這就是存取裝置得以影響運算能力的原因。

可以到達的狀態？

如果一台機器完全沒有存取裝置，也就是完全沒有記憶能力，只看得到目前的狀態，那它還可以運算嗎？嗯！就像拿起一朵有許多花瓣的花，一片一片抽掉，反覆地唸著，「愛我」或「不愛我」這類的問題，應該是可以回答…XD

沒有記憶的機器

a 代表抽掉一片花瓣，1 代表「不愛我」，2 代表「愛好」，如果有這台機器，把花丟給它，若抽掉最後一片花瓣是處於 2，那就恭喜了！

正經一些好了，這台機器的狀態就是運算的結果，若機器處於狀態 2，表示看到奇數個 a，若機器處於狀態 1，表示看到偶數個 a，如果以 2 為接受狀態，這就是台可以判斷 aaaaa 是否為奇數的機器。

進一步地，如果有個字串 abaababaab，想知道其中是否有奇數個 a 呢？

沒有記憶的機器

字串中字元的規律顯然與狀態有關，多一些狀態，可以判斷的字元規律就可以複雜一些，例如，想知道某個二進位編碼，是不是相當於數字 3 的倍數：

沒有記憶的機器

沒有存取裝置的機器，竟然可以進行數字的運算？這是做了餘除器嗎？不！只是判斷 0 與 1 是否以一定的規律輸入，就結論而言，若是由左而右逐位元讀取，觀察 2 進位制下 3 的倍數，發現呈現三種規律：

連續偶數個 1
0 與 0 之間有偶數個 1
10 與 01 之間有任意個 1

下推自動機至少還可以使用堆疊，可以記錄看過幾個符號以便後續消去之用；這邊的機器沒有記憶，只能依規則在狀態之間移動，如果輸入的資料有某種規律，狀態轉移順序也才會呈現規律，也就是說，只有在輸入的資料有規律的情況下，這種機器才有用武之地，你也許想到了 Regular expression，是的！這是 Regular expression 的基礎概念，試著組合幾個這類的機器，可以達到更複雜的模式辨識。

觀察二進位制是否為 3 的倍數，從中發覺規律是難了點，要識別某符號是否以 3 倍長度出現也許比較簡單，基本上就是拿狀態來計數，一個狀態就是一個計數，這個規律很容易發現：

沒有記憶的機器

有限狀態機

像這樣的機器稱為有限狀態機（Finite-state Automaton），要寫個程式來模擬有限狀態機顯然十分容易，因為連存取裝置的模擬都不用，然而要小心，別誤用了不必要的資料結構，使得這機器實際上會記得某些事情，這就不是有限狀態機了。

底下是個實作參考：

class Rule {
    constructor({state, input, nextState}) {
        this.state = state;
        this.input = input;
        this.nextState = nextState;
    }

    isApplicableTo(state, input) {
        return this.state === state && 
                this.input === input;
    }
}

const REJECT = -1;

class Manual {
    constructor(rules) {
        this.rules = rules;
    }

    next_state(state, input) {
        let rule = this.rules
                        .find(rule => rule.isApplicableTo(state, input));
        
        return rule ? rule.nextState : REJECT;
    }
}

class FA {
    constructor(manual, state, acceptables) {
        this.manual = manual;
        this.state = state;
        this.acceptables = acceptables;
    }

    canAccept(text) { 
        let manual = this.manual;
        function digest(state, txt) {
            if(state === REJECT || txt.length === 0) {
                return state;
            } 
            return digest(manual.next_state(state, txt[0]), txt.slice(1));
        }

        let state = digest(this.state, text);
        return state !== -1 && this.acceptables.includes(state);
    }
}

let manual = new Manual([
    new Rule({
        state : 1, 
        input : '0', 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : '1', 
        nextState : 2
    }),
    new Rule({
        state : 2, 
        input : '1', 
        nextState : 1
    }),
    new Rule({
        state : 2, 
        input : '0', 
        nextState : 3
    }),
    new Rule({
        state : 3, 
        input : '1', 
        nextState : 3
    }),
    new Rule({
        state : 3, 
        input : '0', 
        nextState : 2
    })              
]);

let fa = new FA(manual, 1, [1]);
console.log(fa.canAccept('1101110111101'));