- 專欄
文章專區
2019-05-01語言、文法與掠奪性期刊
593 期
Author 作者
游森棚／任教於臺灣師範大學數學系及空軍官校。
形式語言與形式文法
我們先從一個遊戲開始。一開始黑板上寫著一個S，然後，每一步動作為：可以擦掉一個S，然後在被擦掉的位置上寫上ab或aSB。反覆以上動作，直到不能換為止。比如說可以這樣進行：
S→aSb→aaSbb→aaabbb
請問這樣的規則可以換出什麼結果？aaaaaabbbbbb可以用這個規則得到嗎？不難看出，可以得到的結果是形如aa…abb…b（而且a和b一樣多）的字串，而且任意這種字串都能按這個規則得到。
這似乎沒有什麼困難，但是如果規則是這樣：一開始有一個S，然後可以把S換成 aTSc或abc；把Ta換成aT；把Tb換成bb。那請問這樣的規則可以換出什麼結果？可能就不太容易了。讀者可以想一下，答案公布在最後。
其實，這樣簡單的概念背後有非常大的學問，而事實上，讀者看到這裡已經學會語言學與資訊科學中所謂的「形式語言（formal language）」的基礎概念了。
什麼是語言？要有一些字、一些文法和意義，而形式語言就是把這些概念抽象化：
一個「形式語言」包括一些字（words），其組成的字母（letters）取自於一個字母集 （alphabat），且建立於一組明確的規則（稱為形式文法）之上。
以第一個例子為例，就是字母集（{a,b}）上，一些有限長字串的集合（{ab, aabb, aaabbb, aaaabbbb……}）。形式文法是描述這個集合的一種方法（S起頭，每一次可以換成aSb或 ab）。
形式文法（formal grammar）是決定可以得到哪些字串的關鍵。第一個例子中，如果S可換為a或aSb，那生成的形式語言就完全不一樣了。如2個例子所示，我們都是從一個初始符號出發，不斷地應用一些規則，從而生成出不同的字串。
精確來說，一形式文法G可以用G=（N, Σ, P, S）表示。其中：
- 1. N是「非終止符號（nonterminal symbols）」所成的集合，意思是碰到這些符號可以繼續換下去。
- 2. Σ「終止符號（terminal symbols）」所成的集合，意思是這些符號不能再換成其他符號。
- 2. P是一組「產生規則（production rules）」。
- 4. S∈N是一個「起始符號（start symbol）」，為最一開始的種子。
在第一個例子中的文法即
G=（{S}, {a, b}, {S→|aSb|ab}, S）
（這裡S→|aSb|ab表示S可換成aSb或ab）。
在第二個例子的文法即
G=（{S, T}, {a, b, c}, P, S）
其中P包含以下4個規則：
- S→aTSc
- S→abc
- Ta→aT
- Tb→bb
雖然符號化看起來有點嚇人，但讀者應該可以體會這是相當容易的基礎想法。然而，愈基礎的想法影響力就愈大，比如這個文法： ......【更多內容請閱讀科學月刊第593期】