题目
(知识点二)上下文无关文法的产生式形式是 () A. alpha arrow beta (alpha, beta 为任意字符串)B. A arrow alpha (A 为非终结符, alpha 为字符串)C. A arrow aB (a 为终结符)D. A arrow Ba (a 为终结符)
(知识点二)上下文无关文法的产生式形式是 ()
- A. $\alpha \rightarrow \beta$ ($\alpha, \beta$ 为任意字符串)
- B. $A \rightarrow \alpha$ ($A$ 为非终结符, $\alpha$ 为字符串)
- C. $A \rightarrow aB$ ($a$ 为终结符)
- D. $A \rightarrow Ba$ ($a$ 为终结符)
题目解答
答案
B
解析
上下文无关文法（CFG）的产生式形式是该知识点的核心内容。其关键特征是：
- 左边必须是一个单一的非终结符；
- 右边可以是任意字符串（包含终结符和/或非终结符）。
选项B直接对应这一定义，而其他选项或违反左边必须为单一非终结符的要求（如选项A），或仅描述特定形式（如选项C、D中的终结符与非终结符组合），因此正确答案为B。
选项分析
选项A：$\alpha \rightarrow \beta$
- 错误。产生式的左边必须是非终结符，而非任意字符串$\alpha$。例如，若$\alpha$包含多个符号（如$A \to B$），则不符合CFG的定义。
选项B：$A \rightarrow \alpha$
- 正确。符合CFG的核心定义：左边为单一非终结符$A$，右边为任意字符串$\alpha$（可包含终结符、非终结符或空）。
选项C：$A \rightarrow aB$
- 不完整。虽然这种形式（非终结符后跟终结符）可能出现在某些规范形式中（如Chomsky范式），但并非CFG的通用形式。例如，右边可以是纯终结符（如$A \to a$）或纯非终结符（如$A \to B$）。
选项D：$A \rightarrow Ba$
- 同选项C。仅描述了非终结符与终结符的特定组合，未涵盖CFG的全部可能性。