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 + s 與 s + 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.
.