文脈自由文法
文法 G = ( V , Σ , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} の言語は次の集合で表される。
L ( G ) = { w ∈ Σ ∗ : S ⇒ ∗ w } {\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}
ノーム・チョムスキー自身は、生成文法を追加することで文脈自由文法の制限を克服したいと考えていた。
そのような規則も言語学によく見られる。例えば、英語における受動態化である。しかし、それらは強力すぎるため(チューリング完全)、変換の適用は制限される必要がある。生成文法の大部分は、句構造文法と変換規則の記述機構を改善し、自然言語が表現できることを正確に表せるようにすることを目的としている。
彼は自然言語が文脈自由でないと考えていたが、彼がCFGでは不十分であることを示す証拠として挙げた事例は、後に間違いであることが証明された。Gerald Gazdar と Geoffrey Pullum は、一部に文脈自由的でない構造があるものの、自然言語の大部分は文脈自由であると指摘している。文脈自由でない部分とは、例えば、スイスドイツ語の cross-serial dependencies や、バンバラ語の畳語である。