正規文法
正規文法は全ての正規言語を記述することができ、そういう意味では有限オートマトンや正規表現と等価である。さらに言えば、右正規文法も左正規文法も同じ正規言語を定義することができる。
正規文法は全て文脈自由文法に含まれる。
全ての文脈自由文法は、左正規規則と右正規規則の組み合わせに容易に変換可能である。つまり、右正規文法と左正規文法を合成することで全ての文脈自由言語を表現可能である。正規文法は左正規規則か右正規規則を使用するが、同時に両者を使用することはない。そのため、より狭い範囲の言語である正規言語だけを記述できる。
正規文法に空記号(ε)を許さない場合もある。