2018年7月27日 星期五

把 NFA 轉成 DFA 這檔事

故事是這樣子的,最近在時寫一些跟 Regex 相關的程式碼,無意間發現我之前understanding computation 這本書的實作中,並沒有實作非確定有限自動機(下稱 NFA)轉成有限自動機 的程式碼。

所以說我們這次就來實作一下。

概念很簡單,我們手上有一個,我們可以把這個 NFA 拿來,從開始狀態開始,將這個狀態可以接受的字元都走走看,把每一個字元輸入之後的狀態組合都記下來(因為是NFA,同時可以存在許多狀態上),重複這個流程直到所有狀態組合都被記錄過之後, 就能產生對應的 DFA,這個新的 DFA 每一個狀態都會原本 NFA 狀態的組合。
這也代表:其實 NFA 並沒有比 DFA 更「高級」的能力,一切都可以用 DFA 來完成,NFA 只是在表示跟建構上,比 DFA 方便一些而已。

實作一樣使用 Rust 的實作,雖然說也只是照著書上的 ruby code 實作就是了。
在這之前我們已經完成了 FARule, NFARulebook, NFA, NFADesign 等一系列的 struct ,用上了 Rust 的泛型,確保 FARule 可以接受任何型別作為狀態,無論是整數還是一個 struct,這點很重要,這樣我們後面的修改都不用再擔心狀態型別的問題。

首先我們先創了一個 NFASimulation 的 struct,把之前已經實作完成的 NFADesign 塞進去,並加上一個新的函式 to_nfa_with_states,接受一個 NFA 狀態為參數,產生一個以這個狀態為初始狀態的 NFA (一般 NFADesign 產生的 NFA 的初始狀態是固定的)。
接著我們在 NFASimulation 實作兩個函式:next_states 和 rule_for:
  • next_states 會拿到一個 NFA 狀態(HashSet<T>)跟一個字元,回傳的是接受這個字元之後,NFA 新的狀態,注意所謂 NFA 的狀態意思是 DFA 下狀態的組合,因此型態是 HashSet<T>。
  • rule_for 參數是 NFA 狀態,嘗試 NFA 中所有可能的輸入字元,回傳從這個狀態出發,所有可能的規則(FARule)。
最後把上面兩個函式結合在一起,實作 discover_states_and_rules 函式,拿到只有一個初始狀態的集合之後,先呼叫 rule_for 得到所有從這個狀態出發的 rule,將每個 rules 指向的狀態取出來;如果新的狀態集合是輸入狀態集合的子集,表示所有可能的字元輸入都不會得到新的狀態,我們就已經遍歷整個 NFA 了;否則,再把這個狀態集合丟進 discover_states_and_rules 裡面,遞迴直到收集到所有狀態為止。

話是這麼說,但開始實作之後就遇上一個問題,NFA 狀態表示是 HashSet<T>,discover_states_and_rules 的輸入就是 HashSet<HashSet<T>> (NFA 狀態的集合);但 Rust 並不支援 HashSet<HashSet<T>> 這樣的泛型,當我試著從 discover_states_and_rules,設定回傳型別是 HashSet<HashSet<T>> ,rustc 立刻就噴我一臉錯誤,rustc 預設並沒有 HashSet<T> 的雜湊方式,也因此無法把它作為 HashSet 的 key。

當然這是有解法的,後來是參考了下面這個連結
不能直接使用 HashSet<HashSet<T>>,得先把 HashSet<T> 封裝起來,放到名為 StateSet 的 tuple struct 當中,tuple struct 的角色就是單純的封裝,可以用 struct.0 取得第 0 個封裝的元素,也就是封裝的 HashSet<T>。
如此一來我們就可以實作一個 StateSet<T> 使用的雜湊方式,說出來沒啥特別,就是把整個 set 裡面的元素拿出來再雜湊一遍就是了,下面是相關的實作:
use std::hash::{Hash, Hasher}
impl<T: Eq + Clone + Hash + Ord> Hash for StateSet<T> {
  fn hash<H>(&self, state: &mut H) where H: Hasher {
    let mut a: Vec<&T> = self.0.iter().collect();
    a.sort();
    for s in a.iter() {
      s.hash(state);
    }
  }
}

將 HashSet<T> 封裝成 StateSet 之後,就能使用 HashSet<StateSet<T>> 表示 NFA 狀態的集合,從狀態集合到狀態集合的規則,也能用 FARule<StateSet<T>> 表示,這樣就能夠完成 discover_states_and_rules 函式,其返回值是 (states, rules),即型別 (HashSet<StateSet<T>>, Vec<FARule<StateSet<T>>>)。
利用 discover_states_and_rules 一口氣拿到一個 NFA 所有可能的狀態集合,還有對應的規則,就可以產生一個對應的 DFA。
pub fn to_dfa_design(&self) -> DFADesign<StateSet<T>> {
  let start_state = self.nfa_design.to_nfa().current_state();
  let mut start_set = HashSet::new();
  start_set.insert(StateSet::new(&start_state));
  let (states, rules) = self.discover_states_and_rules(&mut start_set);
  let accept_state = states.into_iter()
    .filter(|state| self.nfa_design.to_nfa_with_state(&state.0).accepting())
    .collect();
  DFADesign::new(StateSet::new(&start_state), &accept_state, &DFARulebook::new(rules))
}

在寫這一段程式碼的時候,因為是看著書中的 Ruby 範例程式碼在寫, 其實有很多地方的程式碼還滿像的,例如在 discover_states_and_rules 裡面,除了在型別上面卡關非常久之外,其他語法跟 Ruby 幾乎沒有什麼差別,真不虧是Rust,也許該私下稱 Rust 為「強型別的 Ruby/Python 」XD。
不過呢,在 HashSet<HashSet<T>> 的問題上面,還有例如將兩個 HashSet<T> union 起來上,還是被 rustc 嗆了非常久,真的是深切體會 Python, Ruby 等等知名語言背後到底幫我們處理多少髒東西。

這篇文章相關的原始碼可見:
https://github.com/yodalee/computationbook-rust/blob/master/src/the_simplest_computers/finite_automata/nfasimulation.rs

心得一:我真的覺得,寫 Rust 的話,一定要記得下個 :set matchpairs+=<:> 開啟 <> 的 match,不然看看上面那複雜的嵌套,眼睛直接花掉。
心得二:寫過 Rust 之後再寫 C++ ……,這又醜又囉唆的語言是哪裡冒出來的,超級不習慣,不過就我目前的一點…直覺,我覺得 C++ 如果把過去的東西都拋掉,把 std、reference、smart pointer 用到極致,就會得到一個很像 Rust 但沒有 Rust 記憶體檢查等功能的語言。
心得三:Rust 是世界上最好的程式語言
心得四:頑張るビー (誤

沒有留言:

張貼留言

Related Posts Plugin for WordPress, Blogger...