語意與語法、無限與有限

Roland Backhouse 說:「regular algebra 包含了三個編程的中心概念: 串接、選擇、與重複。因此,它可能是計算科學最基礎的代數結構。」

為什麼 regular expression 這種枯燥的題目得列入 CS 必修?一部分是基於上述 Backhouse 所說的理由。我則想談談最近的一個體悟。

不知為何,我們的正規語言課程教到 regular expression 時很少談到 Brzozowski 的「微分」概念(Brzozowski 1964)。最近重看 Antimirov (1996) 關於 regular expression 的偏微分的 paper, 覺得作者很細心地解釋了重要的細節,很值得一讀 — 是值得所有 CS 學生一讀的程度。

另一部分是regular expression 作為一個最小的例子,點出了許多 CS 人可能沒意識到的觀念:你想要處理的常是某個無限的東西(如 regular language),但你做不到。你只能用有限的符號(如 regular expression)表達它。而這中間一定有差距,於是會發生許多不漂亮的怪事。電腦不知道 r + ss + r 是一樣的;處理一些符號一不小心就停不下來… 你以為這是小雜訊、小問題,但這是許多 CS 問題之所以變得無法速算甚至不可計算的重大差距。

也因為這樣,你得回答許多「這兩個符號表達的東西到底是否相等」的問題。「等於」這個概念之所以那麼難,就是因為它是連接無線與有限的關鍵。

「兩個 regular expression 是否表示同樣的 language」不是已經解出來的問題嗎?嗯,怎麼解呢?比如說,你可以做兩個 NFA/DFA, 看他們是否等價。但怎麼做 DFA? 如果你用 Brzozowski 的 derivative, 就得回頭去回答「這兩個 regular expression 是否相等」。

你的程式一不小心便會產生無限多個「應該」表示同樣的 language, 但在語法上不一樣的 expression. 於是你開始加上許多臨時發明的規則把它們減少。然後你開始不太確定這些規則夠不夠用…

這就是語意與語法、無限與有限的差距。練習處理 regular expression 迫使你去意識到、正視這個問題。這樣的問題在 CS 的許多層面上都重複發生,因為以有限的符號處理無限的事物就是我們一直嘗試做的事。

  • Antimirov, Valentin. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155, pp. 291-319, 1996
  • Brzozowski, Janusz A. Derivatives of regular expressions. Journal of the ACM, 11(4), pp. 481-494, 1964.
  • .

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *