2015年4月29日 星期三

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)的先後順序,但在數學理論中是沒有順序的。

[舉例] 個位數四則運算文法
  • $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範式的規則形式
  1. $A \rightarrow BC$ 一個符號變成兩個符號(不能是起始符號)
  2. $A \rightarrow \alpha$一個符號變成一個結束符號(terminal)
  3. $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的概念做碎形圖形藝術!





技術提供:Blogger.