2019年4月29日

語言、文法與掠奪性期刊

游森棚/任教於臺灣師範大學數學系及空軍官校。

(Photo by Lum3n.com from Pexels)
形式語言與形式文法
我們先從一個遊戲開始。一開始黑板上寫著一個S,然後,每一步動作為:可以擦掉一個S,然後在被擦掉的位置上寫上abaSB。反覆以上動作,直到不能換為止。比如說可以這樣進行:

S→aSb→aaSbb→aaabbb

請問這樣的規則可以換出什麼結果?aaaaaabbbbbb可以用這個規則得到嗎?不難看出,可以得到的結果是形如aa…abb…b(而且ab一樣多)的字串,而且任意這種字串都能按這個規則得到。

這似乎沒有什麼困難,但是如果規則是這樣:一開始有一個S,然後可以把S換成 aTScabc;把Ta換成aT;把Tb換成bb。那請問這樣的規則可以換出什麼結果?可能就不太容易了。讀者可以想一下,答案公布在最後。

其實,這樣簡單的概念背後有非常大的學問,而事實上,讀者看到這裡已經學會語言學與資訊科學中所謂的「形式語言(formal language)」的基礎概念了。

什麼是語言?要有一些字、一些文法和意義,而形式語言就是把這些概念抽象化:

一個「形式語言」包括一些字(words),其組成的字母(letters)取自於一個字母集 (alphabat),且建立於一組明確的規則(稱為形式文法)之上。

以第一個例子為例,就是字母集({a,b})上,一些有限長字串的集合({ab, aabb, aaabbb, aaaabbbb……})。形式文法是描述這個集合的一種方法(S起頭,每一次可以換成aSbab)。

形式文法(formal grammar)是決定可以得到哪些字串的關鍵。第一個例子中,如果S可換為aaSb,那生成的形式語言就完全不一樣了。如2個例子所示,我們都是從一個初始符號出發,不斷地應用一些規則,從而生成出不同的字串。

精確來說,一形式文法G可以用G=(N, Σ, P, S)表示。其中:
  1. N是「非終止符號(nonterminal symbols)」所成的集合,意思是碰到這些符號可以繼續換下去。
  2. Σ「終止符號(terminal symbols)」所成的集合,意思是這些符號不能再換成其他符號。
  3. P是一組「產生規則(production rules)」。
  4. S∈N是一個「起始符號(start symbol)」,為最一開始的種子。


在第一個例子中的文法即
G=({S}, {a, b}, {S→|aSb|ab}, S
(這裡S→|aSb|ab表示S可換成aSbab)。

在第二個例子的文法即
G=({S, T}, {a, b, c}, P, S
其中P包含以下4個規則:
  1. SaTSc
  2. Sabc
  3. TaaT 
  4. Tbbb


雖然符號化看起來有點嚇人,但讀者應該可以體會這是相當容易的基礎想法。然而,愈基礎的想法影響力就愈大,比如這個文法:  ......【更多內容請閱讀科學月刊第593期】