如何構造上下文無關文法？

01-14

L3 = {w1cw2cw3|w1,w2,w3 ∈ {a, b} and the number of a』s in w1 is equal to the
number of b』s in w2}.
求L3的上下文無關文法。不需要答案，求大神指導一下解題方法。

先明確一下題意：應該是 $w_1,w_2,w_3 in {a,b}^*$ 吧，要是 ${a,b}$ 的話枚舉一下語言 $L_3$ 的所有串就行了……

顯然 $w_3$ 在這裡沒什麼用，我們只需構造出 $w_1cw_2$ ，然後接上 $cw_3$ 就行，也即：

$S ightarrow S_1cS_2$ ，

其中 $S_1$ 用於生成生成語言 $L_1 = {w_1cw_2 | ext{# of a$ ， $S_2$ 用於生成 $w_3$ ，也即 $Sigma^* = {a, b}^*$ 。然後分別構造 $S_1$ 和 $S_2$ 。

先說 $S_2$ （因為它簡單）： $S_2$ 其實是個正則文法，對應的正則表達式是 $(0|1)^*$ ，既然我們想要一個上下文無關文法，那就給它轉成左線性文法好了： $S_2 ightarrow S_2a|S_2b|a|b$ 。這一步構造是顯而易見的。

然後構造 $S_1$ 。首先要明確的一點是CFG的能力：可以對兩項進行計數和比較。這說明CFG是有能力構造出語言 $L_1$ 的。可是到底怎麼計數呢？方法就是給兩邊對稱地添加元素。先看三個例子：

（1）迴文串： $X ightarrow aXa|bXb|epsilon|a|b$

（2）括弧配對： $P ightarrow (P) | PP|epsilon$

（3） ${a^nb^n|nin mathbb{N}}$ ： $T ightarrow aTb | epsilon$

這下明白了吧？要讓 $w_1$ 中的a和 $w_2$ 中的b個數相等，就要：每次給 $S_1$ 左邊添加一個a，就右邊添加一個b。不過考慮到 $w_1$ 中的b和 $w_2$ 中的a是不算數的，上面那句話可以改成：每次給 $S_1$ 左邊添加一個僅包含一個a的串，就在右邊添加一個僅包含一個b的串。