Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular 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

在 Minecraft 裡面幹出一台完整的電腦

Lobsters Daily 上看到有強者在 Minecraft 實做邏輯電路,幹出一台完整的電腦出來 (CPU 的部份應該是 turing-complete 了):

PCWorld 有報導:「This 8-bit processor built in Minecraft can run its own games」。

把影片裡的描述截圖出來:

連分支預測器都出現了:

記憶體就 Minecraft 來說也是超大的 256 bytes:

然後還做了 cache 層,這邊提到的是 data cache:

然後這邊是 instruction cache:

也因為已經相當的 powerful,很多經典遊戲都可以玩,像是俄羅斯方塊:

貪食蛇:

打磚塊:

Connect Four

Auto Scaling 就不能綁個 Lambda 嗎...

看到 AWS 宣佈 Amazon EC2 的 auto scaling 有新花樣:「New – Attribute-Based Instance Type Selection for EC2 Auto Scaling and EC2 Fleet」。

你都有 Lambda 了,就不能整合 Lambda 每分鐘跑一次,讓使用者直接用個 turing complete 的方式自己設計要的 policy 嗎... 會用到 auto scaling 的使用者不會在意 Lambda 的那幾毛錢的。

這樣做對 OKR 是比較好沒錯啦,但用的人已經懶的看了...

用純 HTML + CSS 做出來的踩地雷...

一樣還是 Hacker News Daily 上看到的東西,不過這個東西主要就是趣味性為主而已。這次看到的是純 HTML + CSS 做出來的踩地雷 (Minesweeper),沒有 JavaScript 在內:「css-sweeper from PropJockey」。

自從 HTML + CSS3 證明是 Turing-complete 後,再加上 CSS 本身又一直加各種互動性質的操作,出現這些東西好像不太意外就是了 XDDD

依照他的說明,這邊用到的 CSS 技巧主要是 Space Toggle 這個技巧 (也就是 --toggler 這個),但試著找了對應的文獻說明居然沒翻到,有人可以給個 hint 嗎...

利用隱藏的 form input 加上自動完成功能取得敏感資料

anttiviljami/browser-autofill-phishing 這邊示範了怎麼用隱藏的 form input 與自動完成功能取得敏感資料。在這邊可以看到示範 (把 POST 丟到 httpbin 上看 response)。

想法不算困難,但好像也不是很好防... 關掉 autofill 是比較簡單的解法 (我是裝好瀏覽器就會關掉,不過好像很多人都喜歡用這個功能),所以這個問題就丟回給這些 browser vendor 想了 :o

Google 自動完成... Internet 要毀滅了嗎...

在「What Google autocomplete has to say about the Internet」看到一連串 Google Autocomplete 的圖片,這些建議是表示 Internet 要毀滅了嗎 XDDD

不過這個我喜歡:

ie6 is dead

文章最後提到的這個 XDDD

google is evil