昨天介紹了Regular Expression（正規表達式），今天就來聊聊Regular Expression運作背後重要的機制：Finite State Automata/Automaton（有限狀態自動機）。這個名字聽起來很難、很抽象，但其實FSA是一個簡單、強大的概念，跟很多自然語言處理（NLP）的機制都息息相關。

以下就來簡單介紹FSA到底是什麼～～

FSA是什麼

• FSA可以看做是一個抽象的機器，功能是去處理輸入的字串，讓電腦或機器去處理並理解人類的語言。
• FSA其實可以想像是用一個有方向的流程圖，圖上的一個一個流程就是不同的狀態，連接每個狀態的是箭頭（arc），每個箭頭連接不同的狀態，而輸入的字串就會經由箭頭流向不同的狀態。
• 在FSA的開頭有一個起始狀態（start state），也就是機器開始的地方，中間會根據輸入的字串，經過不同的轉換（transition），最後抵達結束狀態（finish/accepting state）。
• 輸入的字串可以想像成是一條長長的底片，上面有一格一格的照片，每一格裡面放的就是一個一個字元，FSA就會一格一格去讀，並依照規則處理。

FSA的五個要素

1. Q：狀態的有限集合
2. q0：起始狀態
3. F：結束狀態 。
4. 輸入字母表 Σ：輸入的符號或指令集合。
5. δ：轉移函數。

Deterministic vs. Non-Deterministic

在FSA裡面又分為 Deterministic FSA 跟 Non-Deterministic FSA，兩者的差別如下：

• Deterministic
  • 在每個狀態接收到輸入的字元時，都只會有一條明確的路徑抵達下個狀態
  • 狀態不允許 null transition，也就是說每個狀態必須要有一個輸入的字元
• Non-Deterministic
  • 同樣一個輸入，可以有很多不同的路徑抵達不同的狀態
  • 允許 null transition，也就是說機器可以不用處理任何輸入的符號就跳到下一個狀態

➡️ 雖然 Non-Deterministic 看起來多了一點彈性，但是其實兩者有一樣的能力

FSA重要性？

FSA可以應用在以下幾個地方：

• 標記分詞（Tokenization）：透過FSA可以讓一段文本分出一個一個小單位的詞
• 語音辨識：可以識別我們人類說的話，並將它們轉換成文字
• 標記詞性

（還有很多應用，這邊也就不一一贅述）

FSA的功能機制看起來很簡單，但是其實現在很多自然語言處理都是從他的概念延伸而來，像是 Hidden Markov Models 或是更進階的 RNN、LSTM 等。

參考資料：https://www.geeksforgeeks.org/theory-of-computation/introduction-of-finite-automata/