我正在尝试为以下内容创建 CFG：
L = {az n |a ∈ {x, y}* 并且 n = a 中 x 的数量或 a 中 y 的数量}
我不知道如何或从哪里开始。
我理解语言描述是一个 x 和 y 的字符串，后跟一个 z 的字符串，z 的数量必须与 x 或 y 相同。
例子：{xxyxyyxxyzzzzz, yxyxyxyyyzzzzzz, etc...}
这是我的“最佳”解决方案：
S => xSz | ySz | ϵ
我知道这是错误的，因为 z 产生相同数量的 x 和 y 组合，而不是单独产生 x 或 y。
编辑：
我认为这是答案，但我不确定。它似乎工作。
S => xSz | ySz | xS | yS | ϵ
编辑：
好吧，那是行不通的，因为它也接受无效的字符串...
我假设您的问题可以分解为两种语言的结合
L=L 1 UL 2
L 1是 (x i ,y j )z k其中 i==k 并且 L 2满足j==k
换句话说，L 1包含相等的 x 和 z，而 L 2包含相等的 y 和 z。
因此，对于 L 1，我们可以将 CFG 组成为
S 1 => A 1 S 1 z | 乙1
A 1 => A 1 B 1 | B 1 A 1 | X
B 1 => yB 1 | e
前 2 个产生式确保它产生相同数量的 x 和 z；
同样，我们可以为 L 2构造 CFG ：
S 2 => A 2 S 2 z | 乙二_
A 2 => A 2 B 2 | B 2 A 2 | 是的
B 2 => xB 2 | e
最后，我们可以联合这些产生式来得到答案：
S => S 1 | 2 _
我认为这是答案：
S = A | B
A = C xSz | C
B = D ySz | D
C = yC | e
D = xD | e
不确定是否可以减少