生成函數 (II) – 關於 RegExp 的妙用

之前說要讀 Analytic Combinatorics 然後寫心得，後來卻跳槽去看代數拓撲，斷尾了。作為一個半途而廢的勞山道士，還是學到了一些粗淺卻酷炫的穿牆術，在此作一些心得分享。內容主要是

1. 免思考，機械化寫出 regexp 的生成函數，進而回答「regexp 所表示的語言中，長度為 $k$ 的字串有幾個？」
2. 初步判斷生成函數係數的漸進複雜度

這兩個手法看起來很酷炫，又在本書 Part I 與 Part II 的第一個章目，的確像是《聊齋誌異》中《勞山道士》的「穿牆術」，很有淺嘗即止的味道。

• RegExp 的生成函數
  • 形式語言的生成函數
  • 正規語言的建構
    • 聯集
    • 串接
    • Sequence
  • 生成函數的建構
    • 聯集與相加
    • 串接與相乘
    • Sequence
  • 舉例
• 初步判斷生成函數係數的複雜度
  • 手法
  • 舉例
    • 費氏數列
    • 形式語言的例子
  • 關於細節

RegExp 的生成函數

形式語言的生成函數

寫出一個正規表達式（RegExp），就代表一個正規語言 $L$。如果 $L$ 中長度為 0 的字串有 $a_0$ 個、長度為 1 的有 $a_1$ 個、長度為 n 的有 $a_n$ 個，則關於 $L$ 的多項式

$$f_{L}(z)=a_0 + a_1z+a_2z^2+...+a_nz^n+...$$

稱為正規語言 $L$ 的生成函數，其第 n 項係數的值是該語言中長度為 n 的字串的數量。

正規語言的建構

雖然在程式語言中，正規表達式有許多花花綠綠的寫法，但是他們都可以由以下三種 regular constructions 來延伸，這裡先明確的寫出來：

聯集

聯集是「或」的概念，用直槓 | 來表達。正規表達式 (a|bb) 可以 match 字串 a 或 bb。

串接

串接是將兩個字串接在一起，寫法是直接接起來。正規表達式 (a|bb)c 代表「a 或 bb 後面要接一個 c」 才 match。

Sequence

Sequence 是指某個字串重複出現，出現次數可以從零次到任意多次，用星號 * 來表達。正規表達式 (a|bb)* 可以 match 空字串、a、aa、abbabb 等。

以上三個就是基本的 regular construction。能夠只以 regular construction 建構的語言稱為 regular language。

生成函數的建構

三種 regular construction 都對應到一種生成函數的運算：| 號對應函數相加的動作，串接是相乘，* 則是把函數 $f(z)$ 寫成 $\frac{1}{1-f(z)}$。以下一一詳細解釋：

聯集與相加

現在有兩個正規語言

$$L_1=\{a\}，L_2=\{bb\}$$

，其生成函數分別為

$$f_{L_1}(z)=z，f_{L_2}(z)=z^2$$

，則他們聯集的新語言 $L_3= \{a, bb\}=$ (a|bb) ，含有長度為一、二的字串各一個，故生成函數為

$$f_{L_3}(z)=z+z^2$$

恰好是 $f_{L_1}(z)，f_{L_2}(z)$ 的和。我們觀察到「正規語言的聯集，對應到生成函數的相加」。

這裡有個但書：語言 $L_1$、$L_2$ 的聯集能表示成生成函數相加，前提是他們互斥。上面的例子如果 $L_2 =$(a|bb) ，生成函數的相加就會出錯。

Correspondence 1：正規語言的聯集，其對應的生成函數相加，但被聯集的兩個語言需互斥。

串接與相乘

Correspondence 2：正規語言的串接，其對應的生成函數相乘。

舉例來說：(a|bb) 的生成函數是 $z+z^2$，而 c 的生成函數是 $z$，因此正規語言 (a|bb)c$=\{ac, bbc\}$ 的生成函數是

$$z^2+z^3 = (z+z^2)\cdot z$$

Correspondence 2 果然所言不假。

Sequence

Correspondence 3：正規語言 $L$ 的生成函數是 $f_L(z)$，則 $L^*$ 的生成函數為 $$\frac{1}{1-f(z)}$$

舉例來說：如果正規語言 $L=$ (a|bb)，則 $L^*=$ (a|bb)*$=\{\epsilon, a, bb, aa, abb, bba, bbbb, ... \}$。我們把這看成

 $L^*=$ ()+(a|bb) + (a|bb)(a|bb)+(a|bb)(a|bb)(a|bb)+…

於是生成函數是

$$f_{L^*}(z)=1+(z+z^2)+(z+z^2)^2+(z+z^2)^3+...$$

，用無窮等比級數公式化簡得到

$$f_{L^*}(z)=\frac{1}{1-(z+z^2)}$$

與 Correspondence 3 所說的如出一轍。

舉例

隨便舉一個有點複雜的 RegExp 來試試：(0|(1(01*0)*1))* 所表示的語言中，長度為 4 的字串有幾個？

我們先寫出其生成函數。一個步驟一個步驟做，從裡面開始：

• (01*0) 對應到 $z\cdot \frac{1}{1-z} \cdot z$，化簡為 $\frac{z^2}{1-z}$

• (01*0)* 要再寫一次 sequence construction，變成 $\frac{1}{1-(\frac{z^2}{1-z})}$

• (1(01*0)*1) 變成 $z\cdot \frac{1}{1-(\frac{z^2}{1-z})} \cdot z = \frac{z^2}{1-(\frac{z^2}{1-z})}$

• (0|(1(01*0)*1)) 變成 $z + \frac{z^2}{1-(\frac{z^2}{1-z})}$

• (0|(1(01*0)*1))* 變成 $\frac{1}{1-(z + \frac{z^2}{1-(\frac{z^2}{1-z})})}$

一個口令一個動作，就這樣寫完了。不管怎麼寫，它總是可以化簡成兩個多項式相除（有理式），畢竟建構過程中不會有開根號什麼的。

Corollary：Regular Language 的 Generating Function 總是有理式。

方才這個生成函數可以化簡為

$$-\frac{z^2+z-1}{(z-1)(z+1)(2z-1)}$$

將其寫成泰勒展開式（過程省略），可以得到 $1+z+2z^2+3z^3+6x^4+...$ ，所以答案也就是 4 次項係數， 6。

另外(0|(1(01*0)*1))*是從維基百科找的 regexp，其意義為「用二進位表示的三的倍數」。用 4 個 digit 能表示的三的倍數有 0000, 0011, … , 1111，正好有 [16/3]+1 = 6 個，果然計算無誤。

初步判斷生成函數係數的複雜度

一個數列 $\{a_n\}$ 有漸進複雜度，而生成函數的係數是個數列，所以也可以計算係數複雜度，這部分是 Analytic Combinatorics 的重點。我在這裡寫下一個粗略的手法，說明如何判斷「生成函數係數複雜度的指數項」，但不證明。

手法

生成函數 $f(z)=a_0+a_1z+a_2z^2+...$ 約分化簡後，其在複數平面上的不連續點之中，距離原點最近的設為 $\hat{z}$，則其數列 $\{a_n\}$ 複雜度的指數項為 $\operatorname{\Theta}(\frac{1}{|\hat{z}|^{n}})$.

但有個前提是：原點不能是生成函數的不連續點。

這裡說不連續點其實不太好，應該要說奇點，因為這有複分析的意義

約分化簡是要把類似 $\frac{(z-1)^2}{z-1}$ 的式子直接寫成 $z-1$。

所謂「複雜度指數項為 $\operatorname{\Theta}(K^n)$」指的是複雜度為 $\operatorname{\Theta}(K^n\cdot f(n))$，其中 $f(n)$ 比指數項還小，比方說 $3^n\cdot n\operatorname{log}n$ ，其指數項就是 $3^n$。

舉例

費氏數列

費氏數列的生成函數為 $$\frac{x}{1-x-x^2}$$ ，其分母在 $z=\frac{\sqrt{5}\pm 1}{2}$ 為零，所以其不連續點中離原點最近的是 $\hat{z}=\frac{\sqrt{5}- 1}{2}$，其絕對值倒數為 $$\frac{1}{|\hat{z}|}=\frac{\sqrt{5}+1}{2}$$ ，所以費氏數列複雜度的指數項為 $$\operatorname{\Theta}((\frac{\sqrt{5}+1}{2})^n)$$ 。對照費氏數列的通式

$$F_n = \frac{1}{\sqrt5}(\frac{\sqrt{5}+1}{2})^n+\frac{1}{\sqrt5}(\frac{\sqrt{5}-1}{2})^n = \operatorname{\Theta}((\frac{\sqrt{5}+1}{2})^n)$$

可發現確是如此。

形式語言的例子

方才我們有個判斷 3 的倍數的正規表達式(0|(1(01*0)*1))*，其生成函數為 $$-\frac{z^2+z-1}{(z-1)(z+1)(2z-1)}$$ 。其分母在 1、-1、0.5 有根，其中 0.5 離原點最近，其倒數為 2，所以複雜度的指數項為 $\operatorname{\Theta}(2^n)$。

對照起來，能用 $n$ 個 digit 表示的三的倍數有 $[2^n/3]+1$ 個，的確是 $\operatorname{\Theta}(2^n)$。

關於細節

關於不連續點有一些細節，比方說方才我們常在找分母的實根，當作不連續點。但是這個多項式是可以代入複數進去的，所以如果有虛根的話，虛根到原點的距離也要考慮進去。

之所以要把分式先約分，是因為類似 $\frac{(z-1)^2}{z-1}$ 的式子雖然不連續，但是從複分析的角度，其不連續點可以輕易的被「填補」（解析延拓）。

很多式子雖然都是有理式的形式，可以只看分母的根，但也有些不是。比方說出現根號也會造成不連續點。

分母在原點有根時，使用這手法可能會算錯。