上下文無關語言(Context-free language)
上下文無關語言是可以用上下文無關文法(Context-free Grammars, CFGs)定義的形式語言，一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。
- 正式定義為4-tuple(狀態集合$V$、結束狀態$\Sigma$、移動原則$R$、開始狀態$S$)。
- 所有上下文無關語言的集合同一於下推自動機(Pushdown automata)所接受的語言的集合。
- 上下文無關語言所能夠表示的語言範圍比正則語言(regular language)還大。
- 應用上，程式語言的大部份特色都屬於上下文無關語言。不同的上下文無關文法(grammar)在編譯器實作時是有推導(derives)的先後順序，但在數學理論中是沒有順序的。
[舉例] 個位數四則運算文法
- $S \rightarrow SAS$
- $S \rightarrow (S)$
- $S \rightarrow 0$
- $S \rightarrow 1$
$...$ - $S \rightarrow 9$
- $A \rightarrow +$
- $A \rightarrow -$
- $A \rightarrow ×$
- $A \rightarrow ÷$
曖昧文法 Ambiguous Grammar
我們可以「剖析(Parse)」一個字串，逐字對應至文法、確立語法，進而判斷原本字串是不是語言當中的字串。字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法(Ambiguous Grammar)」。
- Ambiguous : terminal 形容一個 "string" 有一個以上的 parse tree 可以對應
- inherently ambiguous : 形容某一種 "language" 用grammar寫出來時必是ambiguous
曖昧文法範例[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範式的規則形式
- $A \rightarrow BC$ 一個符號變成兩個符號(不能是起始符號)
- $A \rightarrow \alpha$一個符號變成一個結束符號(terminal)
- $S \rightarrow \varepsilon$起始符號可變空字串(如果語言本來包含空字串)
上下文無關轉成Chomsky範式的舉例[2]
CYK演算法(Cocke–Younger–Kasami algorithm, CYK algorithm)
- 用來判定任意給定的字符串$w \in \Sigma^*$ 是否屬於一個上下文無關文法的算法。普通的回溯法（backtracking）在最壞的情況下需要指數時間才能解決這樣的問題，而CYK演算法只需要多項式時間就夠了（$O(n^3)$ ， $n$ 為字符串 $w$ 的長度）。
- CYK演算法採用了動態規劃的思想。
- 對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，但首先要將該文法轉換成喬姆斯基範式。
Reference
交大陳穎平教授正規語言講義
演算法筆記 - Language
wiki - 喬姆斯基範式
Context Free Art - 有趣的網站，可以用context-free的概念做碎形圖形藝術!
發表文章
沒有留言:
張貼留言