1樓：
這兩種構造當然是等價的，但是第二種更好：
initial state沒有ingoing transition，並且final state沒有outgoing transition
至於為什麼這是個好的feature，題主可以嘗試一下把乙個稍微複雜的正規表示式轉換成NFA再轉換成DFA（ 例如((ab)*|(a(bc)*|(ac)*)*)*)，你就知道為什麼要用第二種構造了。
2樓：
有問題，龍書上這種構造方法都有乙個假設，圖2的 i 節點只有出口，f 節點只有入口，這樣在連線的時候才不會出錯
比如 a*b*，如果按圖一的做法，有可能匹配到 abab但是如果按照圖二的作法，就能正確匹配到 a*b* 了@vczh 是不是這樣？
3樓：大妖精
你這樣連區域性沒問題但是整體有可能出坑（如果其他地方也無腦省略的話）。其實這種省略根本不能簡化你的演算法，效能提公升往往也是有限的。
4樓：ken lan
第一幅圖好像沒有終結點喲。
然後我想說的是，你要想更簡潔，後面整體轉DFA那就是更簡潔的了，然後再最簡化DFA，那就又更簡潔了。
其實本來NFA與DFA比，如果沒錯的話NFA是可以有ε傳遞的，而DFA不行，這也是NFA的乙個特性。
有時候NFA太過簡潔，後面轉DFA手殘搞出問題時可能從圖1中比較難找出來。
NFA是能夠用來幫助我們下一步DFA的操作，如果NFA搞得那麼難debug，那不是為難自己嗎。
所以我覺得要適當的閉包可能會比較好。
逃一波)
5樓：梨梨喵
實際上你確實可以這麼做噠喵.
不會有什麼問題.
為什麼需要引入新的節點乙個很重要的原因是為了保持NFA結構的不變性(immutability), 保持不變性對於證明構造的正確性是非常重要的, 如果破壞了不變性, 那麼對構造演算法的正確性證明將會變得很複雜. 如果你使用純函式式程式設計應該很能體會不變性這一點.
若從抽象的角度看, 對封裝好的子結構進行拆包修改是不符合封裝原則的.
拋開理論方面的原因, 實現上來說新增新節點保留了更多資訊, 同樣更易於實現與更易於拓展. 比如需要實現貪婪匹配(greedy match), 惰性匹配(lazy match), 原子匹配(atomic match)的話需只需要在頭尾兩個節點上新增資訊而不是在邊上新增資訊. 修改拓展節點資料結構相較於修改邊資料結構容易實現與容易除錯多了.
從效率和優化角度來看, 若是直接新增邊而不引入新節點的話, 節點的邊數目是不確定的, 這時候每個節點需要乙個list來儲存所有的邊. 在進行匹配時每個節點都需要對list進行一次遍歷, 遍歷必然包含更多的分支結構和記憶體訪問, 將會帶來額外的開銷, 甚至比引入乙個新節點的開銷還要大. 同樣list結構會帶來額外的記憶體開銷.
當然啦, 你可以選擇進一步將NFA編譯成線性表示的bytecode來消除兩者的效能差異. 不過呢, 引入新節點的編譯實現同樣是比不引入新節點更簡單的.
比較一下兩種節點設計, 你覺得那種更優雅呢喵?
兩種方式都實現實現一遍相信你會體會到噠.
乙隻死在洗澡過程中的貓，這合理麼？
路飛索隆親媽 貓咪是自潔型動物，只要他不出家門，家裡保持乾淨整潔，可以不需要洗澡的。貓咪，特別是膽小的貓咪，會有應激反應的，陌生的人陌生的環境陌生的事情，都會對他們造成可大可小的影響，或是影響性格，或是造成一輩子的陰影，甚至是致命。 說實話，合理。自己之前養過乙隻小貓，是物件在七夕節送的禮物，取名叫...
思維認識過程中的問題？
哲不斷 思維模式大致分為兩種慣性，舉例如下 1.變化 矛盾 和諧思維 認為事物在不停變化沒有永久的對與錯，事物都是由對立面組成的和諧體。比較典型的是道家思維，中庸之道 2.同一 非矛盾 排中性思維 基本核心是認為事物的本質不會變化，一件事不會同時對和錯。比較典型的是西方人的思維 科學思維為什麼從西方...
人類在學習語言到底過程中是如何理解什麼這個詞是什麼意思的？
已登出 什麼 或啥 是最基本的疑問詞 或疑問詞根 跟其他詞綴或詞結合 如什麼人，什麼時間，什麼樣等等 可以問各種問題。類似的，英語的wh 來自原始印歐語kw 日語的nan 都是疑問詞根 maravilloso 這個問題很有趣。我可以根據索緒爾的語言學理論來嘗試回答這個問題。索緒爾有能指和所指的理論，...