Formal Language - Ch6 上下文無關語言 Context-free language, CFLs

上下文無關語言(Context-free language)
上下文無關語言是可以用上下文無關文法(Context-free Grammars, CFGs)定義的形式語言，一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。

正式定義為4-tuple(狀態集合 $V$ 、結束狀態 $\Sigma$ 、移動原則 $R$ 、開始狀態 $S$ )。
所有上下文無關語言的集合同一於下推自動機(Pushdown automata)所接受的語言的集合。
上下文無關語言所能夠表示的語言範圍比正則語言(regular language)還大。
應用上，程式語言的大部份特色都屬於上下文無關語言。不同的上下文無關文法(grammar)在編譯器實作時是有推導(derives)的先後順序，但在數學理論中是沒有順序的。

[舉例] 個位數四則運算文法

曖昧文法 Ambiguous Grammar

我們可以「剖析(Parse)」一個字串，逐字對應至文法、確立語法，進而判斷原本字串是不是語言當中的字串。字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法(Ambiguous Grammar)」。

曖昧文法範例[1] 四則運算運算子無先後順序時

右樹 : $S \rightarrow S+S \rightarrow a+S \rightarrow a+S*S \rightarrow a+a*S \rightarrow a+a*a$
左樹 : $S \rightarrow S*S \rightarrow S+S*S \rightarrow … \rightarrow a+a*a$

曖昧文法範例[2] 自然語言範例

夏天能穿多少穿多少
冬天能穿多少穿多少

喬姆斯基範式(Chomsky Normal Form)

所有的Chomsky範式的文法都是上下文無關，反過來，所有上下文無關文法都可以有效的變換成等價的 Chomsky 範式的文法。

在語言和可計算性領域中很多證明採用了 Chomsky 範式。這些性質還產生了基於 Chomsky 範式的文法的各種有效算法；例如，判定給定字符串是否可以被使用 Chomsky 範式的給定文法生成的 CYK算法。

Chomsky範式的規則形式

上下文無關轉成Chomsky範式的舉例[2]

CYK演算法(Cocke–Younger–Kasami algorithm, CYK algorithm)

用來判定任意給定的字符串 $w \in \Sigma^*$ 是否屬於一個上下文無關文法的算法。普通的回溯法（backtracking）在最壞的情況下需要指數時間才能解決這樣的問題，而CYK演算法只需要多項式時間就夠了（ $O(n^3)$ ， $n$ 為字符串 $w$ 的長度）。
CYK演算法採用了動態規劃的思想。
對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，但首先要將該文法轉換成喬姆斯基範式。