为所有单词的语言 L 找到上下文无关文法 (CFG)，使得单词中的每个终结符在可能较大的字母表 Σ 上出现偶数次
我的长期方法是（唯一的非终结符是 S）：
S ⟶ ε | 党卫军
x ∈ Σ : S ⟶ xSx
x,y ∈ Σ : S ⟶ xxSyy | yySxx | xySxy | xySyx | yxSyx | yxSyx
这个对吗？产生式生成正确的单词，它们会生成所有单词吗？
编辑：大字母表上的 CFG 能否描述一种语言，每个终端出现偶数次？
EDIT_2：如果存在解决方案，乔姆斯基范式是否可能是 |Σ| 中的多项式？?
甚至有一个常规的语法来实现这一点。由于每个常规语法根据定义都是上下文无关的，因此答案是“是”。也可以构造一个有限自动机，但既然你要求一个语法......
方法如下：回想一下，常规语法允许 A -> b C 或 A -> b 或 A -> epsilon 形式的规则，其中 A 和 C 是非终结符，b 是终结符。这实质上意味着每个非终结符都会生成一个终结符，另一个非终结符将生成字符串的其余部分；我们可以说每个非终结符都对它生成的字符串的某个属性进行编码。
现在考虑字母 Sigma 的所有子集。由于 Sigma 应该是有限的，因此子集集（幂集）也是有限的。设非终结符集为 Sigma 的幂集。
从规则开始：{} -> 每个终端 a 的 {a}。对于每个非终结符 X，如果 a 在 X 中，则添加规则 X -> a X-{a}；或 X -> a X+{a} 如果 a 不在 X 中（我草率地写 + 和 - 在这里设置联合和差异）。
最后，添加 {} -> epsilon（空词）。
文法在其非终结符中准确地编码了以奇数出现的终结符集，因此必须再次“取消”。