文脈自由文法
空の文字列を生成しない文脈自由文法は等価なチョムスキー標準形かグライバッハ標準形に変換できる。ここでいう「等価」とは同じ言語を生成するという意味である。
チョムスキー標準形文法は生成規則が単純なので、この標準形は理論的にも実用上も密接な関係がある。例えば、ある文脈自由文法についてチョムスキー標準形を使うことで多項式時間のアルゴリズムで入力された文字列がその文法で生成されるものか否かを判定できる(CYKアルゴリズム)。
次の例は { a n b m c m + n : n ≥ 0 , m ≥ 0 } {\displaystyle \{a^{n}b^{m}c^{m+n}:n\geq 0,m\geq 0\}} である。これは正規言語ではなく文脈自由言語である。以下の生成規則で生成される(この生成規則は文脈自由文法にしたがっている)。
S → aSc | B B → bBc | ε