L = {a^mb^nc^k: k = m×n} 的 CFG
CFG for L = {a^mb^nc^k: k = m×n}
我们可以为这种语言编写 CFG 吗？我搜索了多个网站，但找不到任何答案。
我们可以证明这不是 context-free 使用 context-free 语言的抽取引理，如下所示。
假设语言是 context-free。然后我们就可以用 w = uvxyz where |vxy| 的语言来写任何字符串 w <= p, |维| > 0 并且对于所有整数 k >= 0，u(v^k)x(y^k)z 也是该语言中的字符串。
考虑字符串 a^(2p) b^(3p) c^(6p^2)。这是我们语言中的一个字符串，因为 2p x 3p = 6p^2。现在，考虑放置子串 vxy 的五种情况：
- vxy 仅由 a 组成。抽气至少 1 将使乘积至少减少 3p，打破不等式。
- vxy 仅由 a 和 b 组成。 Pumping down 会使乘积至少减少 2p，打破不等式。
- vxy 仅由 b 组成。 Pumping down 会使乘积至少减少 2p，打破不等式。
- vxy 由 b 和 c 组成。如果我们抽空，我们必须移除至少一个 b 但不超过 p c；因为我们需要删除至少 2p c 以保持相等性为真，这打破了它。
- vxy 仅由 c 组成。 pumping down 减少乘积而不减少被乘数，不能保持相等。
在所有五种可能的情况下，我们看到在抽空（选择 k = 0）时无法保持相等，因此我们的串无法抽空。但是那么语言就不能是context-free.
我们可以为这种语言编写 CFG 吗？我搜索了多个网站，但找不到任何答案。
我们可以证明这不是 context-free 使用 context-free 语言的抽取引理，如下所示。
假设语言是 context-free。然后我们就可以用 w = uvxyz where |vxy| 的语言来写任何字符串 w <= p, |维| > 0 并且对于所有整数 k >= 0，u(v^k)x(y^k)z 也是该语言中的字符串。
考虑字符串 a^(2p) b^(3p) c^(6p^2)。这是我们语言中的一个字符串，因为 2p x 3p = 6p^2。现在，考虑放置子串 vxy 的五种情况：
- vxy 仅由 a 组成。抽气至少 1 将使乘积至少减少 3p，打破不等式。
- vxy 仅由 a 和 b 组成。 Pumping down 会使乘积至少减少 2p，打破不等式。
- vxy 仅由 b 组成。 Pumping down 会使乘积至少减少 2p，打破不等式。
- vxy 由 b 和 c 组成。如果我们抽空，我们必须移除至少一个 b 但不超过 p c；因为我们需要删除至少 2p c 以保持相等性为真，这打破了它。
- vxy 仅由 c 组成。 pumping down 减少乘积而不减少被乘数，不能保持相等。
在所有五种可能的情况下，我们看到在抽空（选择 k = 0）时无法保持相等，因此我们的串无法抽空。但是那么语言就不能是context-free.