雖然題目是英文，但內容是中文的。因為不知道context free grammar的中文。
雖然context free grammar是計算機理論的東西，但原理其實都是數學。以下是一條典型的習題。
以下是五個規矩：
1) S -> SS
2) S -> aSbb
3) S -> bbSa
4) S -> bSaSb
5) S -> e（即empty的意思）
玩法是這樣的。舉例說，你一開始你有一個S。
你可以用 1) 變成SS。
對第一個S你可以用 2)，可變成 aSbbS 。
對上一行的第二個S用 3) ，可變成 aSbbbbSa 。
對上一行的兩個S都用 5)，可變成 abbbba 。
還有一個規矩，就是最後生成的字串是不可以有S的存在。
讀者應該不難知道所有用這五個規矩生成的字串，b的數目是a的數目的兩倍。
但問題來了。是否所有b的數目是a的數目兩倍的字串，都可使用這五個規矩生成出來？
沒有留言:
張貼留言