用automata的path做為memory

最近想整理一下過去修課時散落的心得，就這樣隨時間過去而忘記挺可惜的。

在讀 DFA/NFA 時就有這種感覺，利用 state 的連結方式或某種 path 的展開，可以表示特定記憶狀態，比方若 language 的 size 為有限個，可以把每個 string 以一個 state sequence 表示，於是這些 state sequences 的聯集會成為 state tree，藉此記下整個 language。

這概念運用到 PDA 更有效果，如果想記住 stack 最上層有限個元素，可以在PDA裡加入由2^k個state表示的 tree，記下 stack 裡 top k 元素，像下圖所示：

由 state s 連出的上面那條 path 表示 stack 最上面的元素是 0，下面則表示 1。即使被 pop 掉了，由此延伸，就能同時「多看」幾個 stack 內的元素，比方比較 stack 最上面 3 個和 最下面 3 個是否一樣。由於 PDA 的 state 數是有限個，所以這個做法無法記下無限長的 input string，並且，在建立 state 時就要設計好要記憶多長的內容，比方我們假設最多記 k 個 input，萬一輸入多了一個，這個做法就失效了。所以，在記憶的功能上，這個做法同樣地比不上 Turing Machine，這是先天架構的限制。

以實例來看，FA 和 PDA 都可以判斷部份 ww 類型的字串，只要事先建好長度為 1 ~ k 的 ”state path”，配合 Non-deterministic 的做法 [1]，即可判斷。但我們無法處理任意長度的 w，當 |w| > k時，就無法處理了。

由此想法發展, 我想到 Neural network (NN) 用 node、link、link weight 表示memory，類似的概念在 NN 裡已被提過：linking structure 表示 memory，training 就是將資料記到 linking structure 裡，所以 training 的同時也會破壞 memory。

這個想法很有趣，也能類推到人腦運作，不過不管從正反面來看都有用也有問題。可以說新 input 會造成舊的 knowledge (memory) 被破壞，但也不知道是那個 knowledge 被破壞，也可能是重組成新的 knowledge，隱含可以推論出包含舊有功能和新功能的 knowledge。唯一可以確定的是，link structure 的大小決定了記憶容量。在 FA 和 NN 之間，應該還有更深入的關聯性可以思考，或許可以有系統地分析 NN，從而改進 NN 的不足。

ps

做法：

1. 假設 |w| = i，讀入 i 個 input，並將其「記在」state 裡，舉例來說，s1001表示先前讀到的順序為 1、0、0、1。
2. 往後讀 i 個 input，若讀入的順序和先前「記住」的順序相同，且讀完 i 個 input 後剛好到字串結尾，Accept。

配合 Non-deterministic 的特性，從起點開始會有 k 條叉路，只要有一條猜對|w|，就能正確判斷。