沒有記憶的機器

December 16, 2021

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

可以到達的狀態?

如果一台機器完全沒有存取裝置,也就是完全沒有記憶能力,只看得到目前的狀態,那它還可以運算嗎?嗯!就像拿起一朵有許多花瓣的花,一片一片抽掉,反覆地唸著,「愛我」或「不愛我」這類的問題,應該是可以回答…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'));