這篇稍微偏 CS 理論一些...
以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目，就像是維基百科上的條列：
裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。
前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇，裡面試著用 Perl 的 regular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。
Recursive descent parser 可以當作是 CFG 的子集合，而 CFG 對應到的語言是 CFL，另外他對應到的自動機是 PDA。
我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern)，所以他能接受的 language 已經超過 RL，但我很好奇他能夠做到什麼程度。
用搜尋引擎翻了翻，查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library)：「Which languages do Perl-compatible regular expressions recognize?」。
在裡面有人提到「The true power of regular expressions」這篇文章，裡面給了一個在 PTIME 演算法，將 3SAT 轉換到 PCRE 裡解，這證明了 PCRE 是 NP-hard；另外也很容易確認 PCRE 是 NP，所以就達成了 NP-complete 的條件了...
本來一直以為 PCRE 只是 CFG/CFL/PDA 而已，沒想到這麼強，NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD