隨機上下文無關文法

上下文無關文法（英語：context-free grammar，縮寫為CFG），在計算機科學中，若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式：V->w，則謂之。其中 V∈N ，w∈(N∪Σ)* 。上下文無關文法取名為“上下文無關”的原因就是因為字符 V 總可以被字串 w 自由替換，而無需考慮字符 V 出現的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的。

上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程序設計語言的語法；實際上，幾乎所有程序設計語言都是通過上下文無關文法來定義的。另一方面，上下文無關文法又足夠簡單，使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見LR 分析器和LL 分析器。

BNF（巴克斯-諾爾範式）經常用來表達上下文無關文法。 ^[1] 

上下文有關文法(CSG，英語：context-sensitive grammar)是一種形式文法，其中任何產生式規則的左手端和右手端都可以被終結符和非終結符構成的上下文所圍繞。上下文有關文法比上下文無關文法更一般性，但仍足夠有秩序得可以被線性有界自動機所解析。

上下文有關文法的概念是諾姆·喬姆斯基在1950年代介入的，被作為描述自然語言的語法的一種方式，在自然語言中一個單詞是否可以出現在特定位置上，要依賴於上下文。可以被上下文有關文法描述的形式語言叫做上下文有關語言。 ^[1] 

在計算機科學中，形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。

形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的應用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。 ^[2]