先明確一下題意：應該是吧，要是的話列舉一下語言的所有串就行了……
顯然在這裡沒什麼用，我們只需構造出，然後接上就行，也即：，其中用於生成生成語言，用於生成，也即。然後分別構造和。
先說（因為它簡單）：其實是個正則文法，對應的正則表示式是，既然我們想要一個上下文無關文法，那就給它轉成左線性文法好了：。這一步構造是顯而易見的。
然後構造。首先要明確的一點是CFG的能力：可以對兩項進行計數和比較。這說明CFG是有能力構造出語言的。可是到底怎麼計數呢？方法就是給兩邊對稱地新增元素。先看三個例子：（1）迴文串：（2）括號配對：（3）：這下明白了吧？要讓中的a和中的b個數相等，就要：每次給左邊新增一個a，就右邊新增一個b。不過考慮到中的b和中的a是不算數的，上面那句話可以改成：每次給左邊新增一個僅包含一個a的串，就在右邊新增一個僅包含一個b的串。形式化地寫下來，就是：，其中是僅包含一個a的串，是僅包含一個b的串。至於怎麼構造就不講了吧，非常簡單，它們都是正則文法而已，分別是 和 。（算了還是補上吧： )
當然，上面那個文法是有歧義的，要改成無歧義的好像還挺難=。=不過不要緊，它又沒讓你構造無歧義文法或者證明這個語言是固有歧義的【攤手】
先明確一下題意：應該是吧，要是的話列舉一下語言的所有串就行了……
顯然在這裡沒什麼用，我們只需構造出，然後接上就行，也即：，其中用於生成生成語言，用於生成，也即。然後分別構造和。
先說（因為它簡單）：其實是個正則文法，對應的正則表示式是，既然我們想要一個上下文無關文法，那就給它轉成左線性文法好了：。這一步構造是顯而易見的。
然後構造。首先要明確的一點是CFG的能力：可以對兩項進行計數和比較。這說明CFG是有能力構造出語言的。可是到底怎麼計數呢？方法就是給兩邊對稱地新增元素。先看三個例子：（1）迴文串：（2）括號配對：（3）：這下明白了吧？要讓中的a和中的b個數相等，就要：每次給左邊新增一個a，就右邊新增一個b。不過考慮到中的b和中的a是不算數的，上面那句話可以改成：每次給左邊新增一個僅包含一個a的串，就在右邊新增一個僅包含一個b的串。形式化地寫下來，就是：，其中是僅包含一個a的串，是僅包含一個b的串。至於怎麼構造就不講了吧，非常簡單，它們都是正則文法而已，分別是 和 。（算了還是補上吧： )
當然，上面那個文法是有歧義的，要改成無歧義的好像還挺難=。=不過不要緊，它又沒讓你構造無歧義文法或者證明這個語言是固有歧義的【攤手】