瞎猜的下推機

December 17, 2021

如果想要判斷迴文,也就是從前面往後面,或者從後面往前面讀都相同的一段文字,這件事有限狀態機是做不到的,就算加上瞎猜的能力也做不到,因為判斷迴文必須記得曾經看過哪些符號,才能比對兩側文字是否一一對應。

非確定性下推自動機

這件事看來下推自動機做得到,如果文字寫在紙帶上,有人將紙帶對折並從中剪開,然後用一個代表著中點文字的紙片,再將被剪開的紙帶接合起來,這麼一來,只要將中點紙片前看到的符號放到堆疊,中點紙帶後的文字用來比對、取出堆疊中的文字,若不符合就非迴文,最後若堆疊為空就是迴文。

例如,若文字僅由 ab 兩種符號組成,中點文字為 _,上述的機器可以如下構造:

瞎猜的下推機

不過,機器目的是為了去除人的因素,如果沒有人對折、剪開、接合紙帶,機器就必須有能力自行判斷是否已經讀了一半文字,然後轉移至狀態 2,但是機器無法事先知道文字的長度,又怎麼可能知道什麼時候該轉移狀態…這就只能瞎猜了。

瞎猜的下推機

非確定性轉為確定性

如果機器可以,而且一定可以猜中什麼時候已讀完一半文字,自動轉移至狀態 2,這台機器就可以完成迴文判斷的任務,在規則表示上,這機器可以猜中什麼時候不讀取任何輸入,自動轉移至狀態 2,因而就造成了機器在狀態 1 時有兩個以上可遵循的規則,這樣的神機稱為非確定性下推自動機(Nondeterministic PushDown Automata)。

每次都準確猜中的神機當然是不存在的,就演算法而言是絕對無法設計出來,然而,若能接受運氣不好沒猜中的情況,至少還有能回答「這是迴文」以及「這可能不是迴文」,沒有猜測能力,機器就完全無法判斷迴文了。

這時你可能會想,在〈瞎猜的狀態機〉中曾經談過,一個每猜必中的神奇狀態機,都能轉換為確定性的狀態機,那一個每猜必中的神奇下推機可以轉換為確定性的下推機嗎?

這就要來思考一下,每猜必中的神奇狀態機能轉換為確定性的狀態機,是因為可以合併狀態,也就是執行過程中若機器的環境資訊相同,不過它是讀了多少符號才有了當時的環境資訊,對機器來說都是沒有差別的。

然而,下推自動機的環境資訊中,不單只是狀態,還包含了堆疊目前擁有的符號,下推自動機並沒有限制堆疊的容量,因此就算組態圖中的狀態是有限的,然而環境資訊因為必須包含堆疊,因而不一定可以找出機器運行過程中相同的環境資訊來進行合併,從而不一定能建構對應的確定性下推機。

有限狀態機因為沒有存放裝置,因此環境資訊就只有組態圖中的狀態,合併環境資訊等同於合併狀態來構造出對應的確定性狀態機;下推機因為有存放裝置,不一定有相同的環境資訊可以合併,使用合併環境資訊這條路,來構造對應的確定性下推機不可行。

也許你會想到另一種方式,就是試圖列出各種可能的執行路徑,每個路徑都執行過一遍,看看哪個執行路徑下可以令機器達到接受狀態,這也做不到,每個路徑都執行過一遍的前題時,某路徑執行完後可以將環境資訊回溯至路徑分叉點,然而因為堆疊這個存放狀置,限制了資料只能在堆疊頂端讀寫,一但資料從堆疊中取出,就永遠消失了,又如何能回溯環境資訊呢?

結論就是,非確定性下推機可以處理確定下推機無法處理的問題,就現實而言,加上一個隨機猜測,若結果可以接受「是」、「可能不是」或「可能是」、「不是」的答案,非確定性下推機的構造概念,就算是可以解決問題了。

如果借助圖靈機的能力,可以在套用非確定性下推自動機規則的過程中,收集接下來的可能環境資訊,在輸入完成後,看看最後收集到的可能環境資訊中,是否包含接受狀態,透過這種方式來模擬非確定性下推機,好處是可以直接撰寫非確定性下推機的規則。

不過要小心的是,收集接下來的可能環境資訊並不等於合併環境資訊,接下來的模擬程式也已經不是下推機了,因為它用到了 SimpleSet 這個記憶裝置,只是個方便驗證規則撰寫是否正確的程式:

class SimpleSet {
    constructor(array) {
        this.elems = array.reduce(
            (acc, elem) => {
                return acc.some(e => e.equals(elem)) ? acc : acc.concat([elem])
            }, 
        []);
    }

    get size() {
        return this.elems.length;
    }
}

class Stack {
    constructor(array) {
        this.array = array;
    }

    push(elem) {
        return new Stack([elem].concat(this.array));
    }

    pushAll(elems) {
        return new Stack(elems.concat(this.array));
    }

    pop() {
        return new Stack(this.array.slice(1));
    }

    get top() {
        return this.array[0];
    }

    toString() {
        return this.array.join(' ');
    }    

    equals(that) {
        return this.length === that.length &&
                this.array.map((v, i) => v === that.array[i])
                            .every(eq => eq);
    }
}

class Context {
    constructor(state, stack) {
        this.state = state;
        this.stack = stack; 
    }

    isAcceptable(acceptables) {
        return acceptables.includes(this.state);
    }

    equals(that) {
        return this.state === that.state &&
                this.stack.equals(that.stack);
    }
}

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

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

    next_context(context) {
        let next_stack = context.stack.pop()
                                        .pushAll(this.pushBacks);
        return new Context(this.nextState, next_stack);
    }
}

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

    freeMove(contexts) {
        let frees = new SimpleSet(this.collectContexts(contexts, null));
        return frees.size === 0 ? contexts : frees;
    }

    collectContexts(contexts, input) {
        return contexts.elems
                        .map(context => {
                            return this.rules.filter(rule => rule.isApplicableTo(context, input))
                                                .map(rule => rule.next_context(context));
                        })
                        .reduce((acc, ctxs) => acc.concat(ctxs), []);                  
    }

    next_contexts(contexts, input) {
        let ctxs = this.collectContexts(contexts, input);
        let frees = this.freeMove(new SimpleSet(ctxs));

        return new SimpleSet(ctxs.concat(frees.elems));
    }
}

class Machine {
    constructor(manual, contexts, acceptables) {
        this.manual = manual;
        this.contexts = new SimpleSet(contexts);
        this.acceptables = acceptables;
    }

    canAccept(text) { 
        let manual = this.manual;
        function digest(contexts, txt) {
            if(contexts.size === 0 || txt.length === 0) {
                return contexts;
            } 
            let ctxs = manual.next_contexts(contexts, txt[0]);
            return digest(ctxs, txt.slice(1));
        }

        return digest(this.contexts, text).elems.map(context => this.acceptables.includes(context.state))
                                                .some(acceptable => acceptable);
    }
}

let manual = new Manual([
    new Rule({
        state : 1, 
        input : 'a', 
        top : '$', 
        pushBacks : ['a', '$'], 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : 'a', 
        top : 'a', 
        pushBacks : ['a', 'a'], 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : 'b', 
        top : '$', 
        pushBacks : ['b', '$'], 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : 'b', 
        top : 'b', 
        pushBacks : ['b', 'b'], 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : 'a', 
        top : 'b', 
        pushBacks : ['a', 'b'], 
        nextState : 1
    }),
    new Rule({
        state : 1, 
        input : 'b', 
        top : 'a', 
        pushBacks : ['b', 'a'], 
        nextState : 1
    }),           
    new Rule({
        state : 1, 
        input : null, 
        top : 'a', 
        pushBacks : ['a'], 
        nextState : 2
    }),    
    new Rule({
        state : 1, 
        input : null, 
        top : 'b', 
        pushBacks : ['b'], 
        nextState : 2
    }),       
    new Rule({
        state : 1, 
        input : null, 
        top : '$', 
        pushBacks : ['$'], 
        nextState : 2
    }),       
    new Rule({
        state : 2, 
        input : 'a', 
        top : 'a', 
        pushBacks : [], 
        nextState : 2
    }),  
    new Rule({
        state : 2, 
        input : 'b', 
        top : 'b', 
        pushBacks : [], 
        nextState : 2
    }),           
    new Rule({
        state : 2, 
        input : null, 
        top : '$', 
        pushBacks : ['$'], 
        nextState : 3
    })      
]);

let stack = new Stack(['$']);
let context = new Context(1, stack);
let machine = new Machine(manual, [context], [3]);
console.log(machine.canAccept('babbab'));

再次強調,這個程式在行為上看似非確定性下推機,因為它的規則不是確定性的,然而其實不是非確定性下推,因為程式借助了圖靈機的儲存裝置,才使得結果一定能給出「是」或「不是」的答案,如果不使用圖靈機的儲存裝置,是不可能打造出這種機器的!