生成文法(Generative Grammar)

生成文法は，有限個の終端記号(Terminal Symbol)の集合，有限個の非終端記号(Non-terminal Symbol)の集合，非終端記号のうち特殊な開始記号，有限個の生成規則（Production Rule）からなる．
終端記号は，文法が最終的に生成する文に現れる記号である．以下では，空文字(null character)\(\epsilon\)も終端記号の一つとして扱う．自然言語では，モデル化する対象により，文字、単語などに相当する．配列解析では，塩基やアミノ酸に相当する．
非終端記号は，文法上の抽象的な概念に相当する記号で，自然言語では，句、節などに相当する．
以下，ローマ字大文字は非終端記号，ローマ字小文字は終端記号，ギリシャ小文字は、非終端記号または終端記号あるいはその両方からなる文字列を示す．
生成規則は，以下の形をとる．
\( \alpha \rightarrow \beta \)
ただし，非終端記号または終端記号あるいはその両方からなる文字列\(\alpha, \beta\)は、生成文法の種類ごとに制限がある．

正規文法(Regular Grammar;RG)

正規文法では，生成規則は以下の形を持つ．
\( A \rightarrow xB \) または
\( A \rightarrow x \)
\(A, B\)は非終端記号，\(x\)は終端記号である．

文脈自由文法(Context Free Grammar;CFG)

文脈自由文法では，生成規則は以下の形を持つ．
\( A \rightarrow \beta \)
\(A\)は非終端記号，文字列\(\beta\)には制限がない．

文脈自由文法のチョムスキー標準形

チョムスキー標準形のCFGは，以下の形の生成規則のみからなる．
\( A \rightarrow BC \) または
\( A \rightarrow x \)
任意のCFGはチョムスキー標準形に改造することができる．従ってチョムスキー標準形のCFGに適用される構文解析アルゴリズムは任意のCFG に適用できる．例えば回文のみを生成するCFG の
\( S \rightarrow aSa \)
という生成規則は
\( S \rightarrow W_1 W_2 \\
W_1 \rightarrow a \\
W_2 \rightarrow SW_1 \)
というチョムスキー標準形に展開することができる．