文脈自由言語
文脈自由言語(ぶんみゃくじゆうげんご)とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。
S → E.
E → T | E - T | E + T | (E).
T → T * E | T / E | id | num.
ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。