チョムスキー標準形の文脈自由文法の生成規則の形として、正しい組合せはどれか。ここで、A, B, C は非終端記号、a は終端記号とし、空列の扱いは考えない。

解説

正解は「A → BC と A → a」です。チョムスキー標準形では、すべての規則の右辺が「非終端記号2個」か「終端記号1個」になります。空列を生成しない任意の文脈自由文法はこの形に変換でき、構文木が2分木になるため、CYK 法などの構文解析アルゴリズムや、ポンピング補題の証明に利用されます。「A → aB と A → a」は、正規文法（右線形文法）の規則の形です。「A → aBC と A → a」は、右辺が終端記号1個で始まり非終端記号が続くグライバッハ標準形の規則の例です。「A → BC と A → aB」では、終端記号だけを生成する規則がないため、終端記号だけの列を導出できません。