簡聊DFA（確定性有限狀態自動機）
狀態機理論最初的發展在數字電路設計領域。而在軟體設計領域，狀態機設計的理論儼然已經自成一體。
狀態機是軟體編程中的一個重要概念，比這個概念更重要的是對它的靈活應用。在一個思路清晰而且高效的程式中，必然有狀態機的身影浮現。比如說一個按鍵命令解析程式，就可以被看做狀態機：本來在A狀態下，觸發一個按鍵後切換到了B狀態，再觸發另一個鍵後切換到C狀態，或者返回到A狀態。這就是最簡單的按鍵狀態機例子。實際的按鍵解析程式會比這更複雜些，但這不影響我們對狀態機的認識。進一步看，擊鍵動作本身也可以看做一個狀態機。一個細小的擊鍵動作包含了：釋放、抖動、閉合、抖動和重新釋放等狀態。
1. 狀態機的歷史
純屬個人觀點，如有錯誤請指正
狀態機衍生於離散數學中的圖論，然後針對於特定場景下提出的延伸性概念。
圖論最開始研究的是現實中的事物之間的關係。
比如圖論裡面經典的「七橋問題」，是有具體的事物：4個島嶼，7座橋樑。
隨著科技的進步，發現一些新的事情無法用「事物」來表述。
而電腦程式的狀態機則更加抽象了「事物」的概念，「狀態」即「事物」。「狀態」可以對應獨立事物的狀態，如人的狀態：開心，悲傷，嚴肅，正常等；也可以對應多種事物間的關係，如我愛你，你愛他，他愛我。
我們也把多種事物的狀態抽象成一個獨立的整體，比如「三角戀」，可以當做一個獨立的整體來研究。
其實很多時候我們延伸了狀態的概念，比如數據，或者關係
2.概念
無限狀態機屬於理論上的一個模型，比如人腦，對於目前人類來說就屬於無限狀態機。
現在的人工智慧AI，理論上是要實現的就應該是無限狀態機。可以在任何情況下，做出合理的抉擇。
而目前人工智慧無法「打敗」人類，也是因為狀態是可以被枚舉的。
不可預測是無限狀態機么？
我們主要來研究有限狀態機：狀態可以被枚舉的狀態機。先來統一幾個概念：
- 輸入：有可能觸髮狀態改變的 數據、事件等；每個節點都必須至少有一個輸入；
- 轉換：從一種狀態轉移到另一種狀態之間的過程；「狀態」被轉換以後，可能是一種新態，也可能不變；
- 狀態：從某種維度建立的，描述當前系統、事物等的數據；
- 接受狀態（終態）：被用戶接受的狀態；
- 非接受狀態：中間狀態，不被用戶接受，但現實存在的狀態；
我們要說明的是DFA，即確定性有窮狀態自動機：在輸入一個狀態時，只得到一個固定的狀態。
3. 一個簡單的DFA
人抽煙生病：
-
正常狀態A
-
難受狀態B
-
住院狀態C
-
h：普通抽一支，沒事兒，還是A；
-
i： 抽多了，開始不舒服B；
-
j：檢查出來生病了，肺部損傷住院C；
-
k：趕緊拿掉葯，猛吃；
-
l：開始好轉，回到默認狀態；
此時回到了A（正常）狀態；
下圖的狀態演示圖裡面，表明這個煙民沒有戒煙成功，還是在向C狀態轉移。
其中：
輸入： h ,i ,j,k,l
轉換： 箭頭連線
狀態：A，B，C
非接受態：A,B
接受態：C
我們用數學符號表示：
- M = (Q,Σ,𝛿 )
- Q：有限狀態集合(如 {A,B,C})
- Σ: 有限輸入集合(如{ h,i,j,k,l})
- 𝛿 : 狀態轉換步驟(如 有向箭頭）
為了更進一步區分：
- M = (Q,Σ,𝛿 ,q0,F)
- q0: 初始態（如A)
- F: 接受態集合(如{C})
在狀態機的圖裡面，我們約定：
- 一個圓圈代表 非接受態
- 兩個圓圈代表 接受態
- 箭頭代表轉換函數
- 箭頭字元表示輸入的數據、事件
4.實現狀態機
狀態機主要實現三大要素，
輸入，
轉換，
狀態。
/*
M = (Q,Σ,𝛿 ,q0,F)
Q(別名State,簡寫 S)： 有限狀態集合(如 {A,B,C})
Σ: 有限輸入集合(如{ h,i,j,k,l}),外部輸入
𝛿（別名 Input,簡寫I) : 狀態轉換步驟(如 有向箭頭）
q0: 初始態（如A)
F: 接受態集合(如{C})
！！！！通過輸入驅動的狀態機！！！
*/
export interface DFATransition<S> {
/** 前置態 */
from: S;
/** 目標態 */
to: S;
/** 目標狀態的執行函數 */
toFunc: Function;
}
export class DFA<S, I extends string, T extends DFATransition<S>> {
/**
* 初始狀態
*/
private startState: S = null;
/**
* 當前狀態
*/
private _curState: S = null;
/**
* 接受態（最終態）
*/
private acceptState: S[] = [];
/**
* 狀態切換函數𝛿
*/
private transMap: Map<I, T[]> = new Map();
/**
* 所有狀態集合S
*/
private stateSet: Set<S> = new Set();
/**
* 所有輸入集合Σ
*/
private inputSet: Set<I> = new Set();
constructor(state: S, acceptState: S[]) {
this.startState = state;
this.acceptState = acceptState;
this.resetStart();
}
get curState(): S {
return this._curState;
}
set curState(s: S) {
console.log('[DFA]DFA設置到狀態：', s);
this._curState = s;
}
/**
* 恢復初始狀態
*/
public resetStart(): void {
this.curState = this.startState;
}
/**
* 創建狀態機執行結構;
* 如果已經存在當前結構，則覆蓋：
* 比如，從 a->b已經存在了，這次再次添加，則a->b被覆蓋；
* @param from 開始態
* @param to 目標態
* @param input 轉換條件、事件
* @param toFunc 目標態對應的執行器
* @returns
*/
public add = (from: S, to: S, input: I, toFunc: Function): DFA<S, I, T> => {
// FIXME 不用as T會報錯
let newT = { from, to, toFunc } as T;
let arr: T[] = this.transMap.get(input);
if (!arr) {
arr = [];
this.transMap.set(input, arr);
}
// HACK 效率不高，看著好看,[]也會被執行一遍
let hasCover = false;
for (let i = 0, len = arr.length; i < len; i++) {
let t = arr[i];
if (t.from === from) {
// 為什麼沒有判斷 t.to == to? 因為轉移的條件是 狀態+輸入，目標狀態是確定的；如果加入to，可能能 輸入i+狀態s -》可能會對應不同的結果；
// 如果存在當前轉移
arr[i] = newT;
hasCover = true;
}
}
if (!hasCover) {
arr.push(newT);
}
this.stateSet.add(from).add(to);
this.inputSet.add(input);
return this;
}
/**
* 事件輸入
* @param i
*/
public input = (i: I): boolean => {
let arr: T[] = this.transMap.get(i);
let t: T = null;
if (arr && arr.length) {
// 找到當前轉移
arr.some((item: T) => {
if (item.from === this.curState) {
t = item;
console.log('[DFA]DFA轉移，起始態：' + t.from + '終止態：' + t.to);
this.curState = item.to;
item.toFunc && item.toFunc();
return true;
}
});
}
if (!t) {
console.log('[DFA]DFA無法響應輸入事件，無法處理當前轉移類型：' + i, '當前狀態：' + this.curState);
return false;
} else {
return true;
}
}
/**
* 當前狀態機是否存在對應的狀態
* @param s 被判斷的狀態
* @returns
*/
public hasState(s: S): boolean {
return this.stateSet.has(s);
}
public getStateLen(): number {
return this.stateSet.size;
}
/**
*
* @returns 是否是初始態
*/
public isStartState = (): boolean => this.curState === this.startState
/**
*
* @returns 當前狀態是否被接受
*/
public canAccept = (): boolean => this.acceptState.includes(this.curState)
}
4. 狀態機與狀態模式
都有「狀態」。
狀態機是建模方式，是一種模型；
狀態模式是基於狀態改變行為的設計模式,表示狀態的行為。
5. 應用場景
在項目中嘗試用狀態機製作觸摸。
觸摸包含 ：開始觸摸，touchBegin；觸摸移動，touchMove; 觸摸結束，touchEnd
其中，點擊事件是 touchBegin+touchEnd
實現以後，發現程式碼非常難維護；比如當前物件既有拖動，又有點擊的時候，很難去清晰的進行狀態轉移。會新增一些hack寫法。
6.總結
個人認為狀態機思想是驚為天人的，在一些領域有重要意義。而在前端交互上，用狀態機實現一些東西，容易出現各種問題：
如：設置「偽態」；他人難以維護；新增狀態時需要非常謹慎。
大多數場景下，我們不一定要用他，通過別的方式也可以實現。
內心一定要有它！！！
參考：
自動機，狀態機，有限自動機，有限狀態機，有限狀態自動機，非確定下有限狀態自動，確定性有限狀態自動機的區別於聯繫
//www.voidcn.com/article/p-bgmycagl-de.html
談談狀態機
//zhuanlan.zhihu.com/p/28142401
編譯原理筆記3：有限自動機
//www.jianshu.com/p/afad52d4c5d4
證明與計算(7): 有限狀態機(Finite State Machine)
//www.cnblogs.com/math/p/fsm.html
淺談狀態機原理及其應用
//blog.csdn.net/zhuqiuhui/article/details/102533721?utm_medium=distribute.pc_relevant_download.none-task-blog-baidujs-2.nonecase&depth_1-utm_source=distribute.pc_relevant_download.none-task-blog-baidujs-2.nonecase
【翻譯】遊戲設計模式之狀態機
//zhuanlan.zhihu.com/p/74984237
遊戲狀態機實現介紹
//blog.csdn.net/yonshi/article/details/40082021
技術系列之「狀態機」
//kb.cnblogs.com/page/528966/
狀態機思路在程式設計中的應用
//kb.cnblogs.com/page/528971/
《有限狀態機在開放式數控系統中的應用》
