CFG for L = {a^mb^nc^k： k = m×n}

Question

我们可以为这种语言编写CFG吗?我搜了好几个网站都没找到答案。

Answer 1

我们可以使用上下文无关语言的抽运引理证明这不是上下文无关的，如下所示。

假设语言与上下文无关。这样我们就可以将任意字符串w写成w = uvxyz其中|vxy| <= p， |vy|>0，对于所有整数k>= 0, u(v^k)x(y^k)z也是该语言中的字符串。

考虑字符串a^(2p) b^(3p) c^(6p^2)。在我们的语言中这是一个字符串，因为2p x 3p = 6p^2。现在，考虑放置子字符串vxy:

的五种情况

1. vxy仅由a组成。向下泵入至少一个将使产物降低至少3p，打破了等式。
2. vxy仅由a和b组成。向下压会使积降低至少2p，打破了等式。
3. vxy仅由b组成。向下压会使积降低至少2p，打破了等式。
4. vxy由b和c组成。如果我们往下抽，我们必须去除至少一个b，但不能超过p个c;因为我们需要删除至少2p个c来保持等式成立，这就打破了它。
5. vxy仅由c组成。

在所有五种可能的情况下，我们看到当向下抽运(选择k = 0)时不能保持相等，因此我们的字符串不能向下抽运。但是语言不能是上下文无关的。