形式文法
N {\displaystyle N} 内の記号 S {\displaystyle S} は「開始記号」である。
一般にこのような形式文法 G {\displaystyle G} は 4要素 ( N , Σ , P , S ) {\displaystyle (N,\Sigma ,P,S)} で要約される。
形式文法 G = ( N , Σ , P , S ) {\displaystyle G=(N,\Sigma ,P,S)} の言語は L ( G ) {\displaystyle {\boldsymbol {L}}(G)} と記述され、開始記号 S {\displaystyle S} に P {\displaystyle P} の規則を非終端記号が無くなるまで適用して得られる( Σ {\displaystyle \Sigma } 内の文字から構成される)全ての文字列として定義される。
文脈自由文法では、生成規則の左側にはひとつの非終端記号だけが置かれる。この制限があるため、文脈自由文法はあらゆる言語を生成できるわけではない。文脈自由文法で表現される言語を「文脈自由言語」と呼ぶ。
前述の例で定義された言語は文脈自由言語ではない。これは文脈自由言語の反復補題を使って厳密に証明可能である。 { a n b n | n > 0 } {\displaystyle \left\{a^{n}b^{n}|n>0\right\}} で表される言語(ひとつ以上の 'a' の後に同じ個数の 'b' が続く)を定義する文法 G 2 {\displaystyle G2} を例として考えよう。 G 2 {\displaystyle G2} は N = { S } {\displaystyle N=\left\{S\right\}} , Σ = { a , b } {\displaystyle \Sigma =\left\{a,b\right\}} から成り、開始記号 S {\displaystyle S} と以下の生成規則で定義される。