nfa和dfa的轉換函數有什么區別?
1.DFA對于文本串里的每一個字符只需掃描一次,比較快,但特性較少;NFA要翻來覆去吃字符、吐字符,速度慢,但是特性豐富,所以反而應用廣泛,當今主要的正則表達式引擎,如Perl、Ruby、Python的re模塊、Java和.NET的regex庫,都是NFA的。2.只有NFA才支持lazy和backreference等特性;
3. NFA急于邀功請賞,所以最左子正則式優先匹配成功,因此偶爾會錯過最佳匹配結果;DFA則是“最長的左子正則式優先匹配成功”。
4. NFA缺省采用greedy量詞(見item 4);
5. NFA可能會陷入遞歸調用的陷阱而表現得性能極差。