文脈自由文法の生成規則の形として、適切なものはどれか。ここで、A は非終端記号、α, β, γ は終端記号と非終端記号からなる記号列とする。

解説

正解は「左辺が1個の非終端記号である A → α の形」です。文脈自由文法では、非終端記号 A を、その前後に何があるか（文脈）に関係なく α に書き換えられることから、この名前があります。「前後の記号列を伴う αAβ → αγβ の形」は、前後に α と β がある場合にだけ A を γ に書き換えられる文脈依存文法の規則です。「右辺が終端記号1個、または終端記号1個と非終端記号1個に限られる形」は、A → a や A → aB の形の正規文法（右線形文法）の規則です。「左辺と右辺の長さが常に等しい形」は、どの型の文法の定義でもありません。文法の型は、生成規則に課す制限の違いで区別されます。