形式文法
正規文法でも生成規則の左側はひとつの非終端記号だけが置かれるが、さらに右側も制限が加えられ、ひとつの終端文字か、ひとつの終端文字とひとつの非終端記号から成る文字列のいずれかしか許されない。(広く採用されている定義として、複数の終端文字で構成される文字列か、ひとつの非終端文字のいずれか、という言い方もできる。どちらにしても同じクラスの言語を意味している。)
{ a n b m | m , n > 0 } {\displaystyle \left\{a^{n}b^{m}|m,n>0\right\}} で表される言語(ひとつ以上の 'a' の後にひとつ以上の 'b' が続く)を定義する文法 G 3 {\displaystyle G3} を例として考える。 G 3 {\displaystyle G3} は N = { S , A , B } {\displaystyle N=\left\{S,A,B\right\}} , Σ = { a , b } {\displaystyle \Sigma =\left\{a,b\right\}} から成り、開始記号 S {\displaystyle S} と以下の生成規則で定義される。
生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は曖昧であると言う。
たとえば、' a {\displaystyle a} ' と ' b {\displaystyle b} ' から成る文字セットがあり、開始記号 ' S {\displaystyle S} ' に対して以下の規則を適用するものとする。
1. S ⟶ a S b {\displaystyle S\longrightarrow aSb}
2. S ⟶ b a {\displaystyle S\longrightarrow ba}
そこで、" S {\displaystyle S} " から開始して、適用する規則を選んでいくことができる。規則1を選ぶと、開始記号 ' S {\displaystyle S} ' から ' a S b {\displaystyle aSb} ' に変換されるので " a S b {\displaystyle aSb} " が得られる。
以上のふたつの言語を生成した生成規則の違いとは別に、ふたつの言語 { a n b n | n > 0 } {\displaystyle \left\{a^{n}b^{n}|n>0\right\}} (文脈自由)と { a n b m | n , m > 0 } {\displaystyle \left\{a^{n}b^{m}|n,m>0\right\}} (正規)の高いレベルで見たときの大きな違いは、文脈自由言語では 'a' の個数と 'b' の個数が同じになるということである。つまり、文脈自由言語を理解するオートマトンは正規言語を理解するオートマトンよりも保持すべき情報が多い。正規言語では 'a' や 'b' の個数を数える必要はなく、単にどちらもゼロより多いことだけを確認できればいいのである。
詳細については文脈自由言語と正規言語を参照されたい。