cfg for l = {a^mb^nc^k：k = m＆＃xd7; n}

Question

我们可以为此语言编写CFG吗？我搜索了多个网站，但找不到任何答案。

Answer 1

我们可以证明，使用泵送引理的无上下文语言，这不是不含上下文的。

假设该语言是无上下文的。然后，我们可以用语言编写任何字符串w，因为w = uvxyz where | vxy | ＆lt; = p，| vy | ＆gt; 0，对于所有整数k＆gt; = 0，u（v^k）x（y^k）z也是语言中的字符串。

考虑字符串a^（2p）b^（3p）c^（6p^2）。这是我们语言的字符串，因为2p x 3p = 6p^2。现在，考虑放置子字符串VXY：

1. VXY的五个案例仅由A组成。至少将产品泵送至少会将产品减少至少3便士，从而打破了平等。
2. VXY仅由A和B组成。泵送将至少将产品减少2p，从而打破平等。
3. VXY仅由B组成。泵送将至少将产品减少2p，从而打破平等。
4. VXY由B和C组成。如果我们抽水，我们必须删除至少一个B，但不超过P C。因为我们需要删除至少2p c以保持平等性真实，所以这会破坏它。
5. VXY仅由C组成。泵送会减少产品而不减少无法保持平等性的倍数。

在所有五种可能的情况下，我们都认为平等在抽水时无法保持平等（选择k = 0），因此无法将其串泵向下。但是，语言不能无上下文。