文脈自由文法
Context-free Grammer (CFG)
単語の前後関係に依存せずに導出 → 文脈自由
$ V → $ w
$ V は非終端記号
$ w は終端記号と非終端記号の（0個を含む）任意個の並び
非終端記号
抽象的な文法要素を表現する記号
終端記号
文を直接構成する要素
$ G=(V\,,\Sigma \,,R\,,S\,)
$ Vは変数（非終端記号）の有限集合
$ \Sigmaは終端記号の有限集合で、$ \Sigma \cap V=\Phi
$ Sは開始記号（変数）
$ Rは$ Vから $ (V\cup \Sigma )^{{*}} への関係であり、 $ \exists \,w\in (V\cup \Sigma )^{{*}}:(S,w)\in R が成り立つ