文脈自由文法
文脈自由文法 G は次の 4-タプル で表される。
G = ( V , Σ , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} ここで
V {\displaystyle V\,} は変数(非終端記号)の有限集合
Σ {\displaystyle \Sigma \,} は終端記号の有限集合で、 Σ ∩ V = ∅ {\displaystyle \Sigma \cap V=\emptyset }
S {\displaystyle S\,} は開始記号(変数)
R {\displaystyle R\,} は V {\displaystyle V} から ( V ∪ Σ ) ∗ {\displaystyle (V\cup \Sigma )^{*}} への関係であり、 ∃ w ∈ ( V ∪ Σ ) ∗ : ( S , w ) ∈ R {\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R} が成り立つ
R {\displaystyle R\,} のメンバーを文法の規則と呼ぶ。