含可空非终结符的产生式是否可空？附文法实例求证

1. 若某产生式包含可空非终结符，该产生式是否为可空产生式？ #

答案是不一定，得结合产生式的具体结构判断：

先明确两个核心概念：

• 可空非终结符：存在至少一条推导路径能得到空串ε的非终结符。
• 可空产生式：产生式的右部可以推导出ε的产生式（要么右部直接是ε，要么右部所有符号都能推导出ε）。

举两个例子对比就清楚了：

• 假设产生式为 X → Yc，其中Y是可空非终结符（比如Y→ε）。这个产生式的右部是Yc，c是终结符无法为空，所以整个右部最多推导出c，永远得不到ε——这个产生式就不是可空产生式。
• 如果产生式是 X → YZ，且Y、Z都是可空非终结符，那右部可以推导出εε=ε，这个产生式就是可空产生式。

简单来说：产生式里有可空非终结符不代表它自己能推导出空串，只有当右部所有符号都能为空，或者右部直接是ε时，它才是可空产生式。

2. 给定文法规则：A → aB | ε、B → bA | e，是否因A是可空非终结符，B也可空？ #

答案是B不可空，具体分析如下：

首先，A确实是可空非终结符——因为有直接产生式A→ε，一步就能得到空串。

但看B的所有推导路径：

• 第一条路径：B → bA，A能推导出ε，最终得到bε = b（是终结符，非空）；
• 第二条路径：B → e，这里e是终结符，本身就不是空串。

也就是说，B的所有推导分支最终都只能得到非空的终结符串，没有任何一条路径能推导出ε，所以B不是可空非终结符。

总结：一个非终结符是否可空，取决于它自己有没有推导到ε的路径，哪怕它依赖的其他非终结符是可空的，也不代表它自己一定可空。

内容的提问来源于stack exchange，提问作者user6003740