1樓：AirGuanZ
手頭沒有龍書，不知道它怎麼解釋的，我說一下我的理解。
這個正規表示式的意思是所有「倒數第n個字元為a」的由a和b構成的串。由於dfa不知道輸入串什麼時候會結束，因此它必須記住最近看到的n個字元各自是什麼，這樣才能在輸入結束的時候知曉倒數第n個字元是否是a。由於最近看到的n個字元共有2^n種可能的取值，所以dfa至少要有這麼多個狀態。
基於這樣的想法，證明這一命題就很容易了。假設有一台只有2^n-1個狀態的dfa，那麼在串集(a|b)^n之中至少有兩個不同的串會使得該dfa讀完最後乙個字元後處於相同的狀態。記這兩個串分別為A和B，不妨設它們的的前k個字元相同，A的第k+1個字元為a，B的第k+1個字元為b。
我們在兩個串末尾各自再追加一些a，使得第k+1個字元恰好是倒數第n個字元，並記追加後的串分別為A'和B'。那麼，串A'的倒數第n個字元是a，應該被此dfa接受，反過來B'應被拒絕。然而，dfa在讀到A'或B'的第n個字元時處於同乙個狀態，後續字元又都是a，它一定會為A'和B'給出同乙個判定結果，這是不正確的。
正規表示式生成
今天剛好研究了自動生成js正規表示式的工具 試試randexpnpminstall randexp node demo.js varRandExp require randexp must require on node supports grouping and pipingnewRandExp ...
應該怎麼練習使用正規表示式？
鵬鵬李李 這個問題我來回答 我是自己搞了乙個object parse string 這麼一套庫，然後tokenizer longlongstring 的 其中基本資料型別的全是用string型別，當時我就想到用正規表示式來表示資料型別，也就是元資料。而且這個方案嚴謹性還算不錯，就是匹配處理速度太慢了...
正規表示式攻擊 ReDoS 如何預防？
小小的寂寞 支援自定義萬用字元的站內搜尋功能有可能受到類似攻擊。當然我是說理論上。可以把有可能出現 ReDoS 的部分用單獨 worker 執行緒做 如果用 Node 的話，其他回答中說是多程序 並且配置伺服器集群以降低這個問題可能帶來的危害。 舒辰 不是太理解為什麼會存在這個問題，記得正規表示式和...