瞎猜的下推機
December 17, 2021如果想要判斷迴文，也就是從前面往後面，或者從後面往前面讀都相同的一段文字，這件事有限狀態機是做不到的，就算加上瞎猜的能力也做不到，因為判斷迴文必須記得曾經看過哪些符號，才能比對兩側文字是否一一對應。
非確定性下推自動機
這件事看來下推自動機做得到，如果文字寫在紙帶上，有人將紙帶對折並從中剪開，然後用一個代表著中點文字的紙片，再將被剪開的紙帶接合起來，這麼一來，只要將中點紙片前看到的符號放到堆疊，中點紙帶後的文字用來比對、取出堆疊中的文字，若不符合就非迴文，最後若堆疊為空就是迴文。
例如，若文字僅由 a、b 兩種符號組成，中點文字為 _，上述的機器可以如下構造：
不過，機器目的是為了去除人的因素，如果沒有人對折、剪開、接合紙帶，機器就必須有能力自行判斷是否已經讀了一半文字，然後轉移至狀態 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'));
再次強調，這個程式在行為上看似非確定性下推機，因為它的規則不是確定性的，然而其實不是非確定性下推，因為程式借助了圖靈機的儲存裝置，才使得結果一定能給出「是」或「不是」的答案，如果不使用圖靈機的儲存裝置，是不可能打造出這種機器的！
