我如何证明以下语言是（不是）上下文无关的？它不规则的论点如下。
我怀疑这种语言是上下文无关的......我之所以这么认为，是因为 L = {a n b m c {n+m} | n,m >= 0} 是上下文无关的。可以在以下位置找到证明
http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf（pdf中的 p102；文本中的 p94）
证明有点长，并且可以通过使用与 PDA 的等价性来证明它的时间要短得多（即首先将某个符号 n “+” m 次推入堆栈，然后再将其取出 n+m 次。）不管怎样，这个例子让我相信我的原始语言也必须是上下文无关的。然而，我真的不明白我该如何为此争论。
不，您的假设不正确！
该语言L = { x = y + z | where x, y, z are binary integers and x is the sum of y and z}不是上下文无关语言（CFL） 。
我试图解释。
首先，考虑以下示例字符串s语言L。
110 = 100 + 10
1110 = 1100 + 10
:
111000 = 110000 + 1000
在我的解释中，LHS 是X有问题的，而 RHS 是 Y + Z。
什么是为 CFL 抽引理？
如果语言 L 是上下文无关的，则存在某个整数 p ≥ 1 使得 L 中的任何字符串 s 与 |s| ≥p。（其中 p 是“泵送长度”可以写成
s = uvxyz
with substrings u, v, x, y and z, such that
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uv nxy nz is in L for every natural number n.
这个定义 | ≥ 1 和 3。对于每个自然数 n，uv nxy nz 都在 L 中。
注意：中间部分s，vxy不大于抽水长度p。（条件一）
[解决方案]：
让我们选择一个满足条件 s的字符串L|s| ≥ p
我们 s是 1 m 0 q = 1 m-1 0 q + 10 q , 其中 q > p , m-1 > p
现在总长度s大于 2m + 2q -1，p当然对于自然数的某些组合，这种不等式是可能的（我不包括长度+和=保持解释简单）
现在s，根据 CFG 的抽取引理，我们的语言已经足够大了。
现在打破它：
u vxy z = 1 m 0 q = 1 m-1 0 q + 10 q
尝试用 L 语言查找v并y抽取和生成新字符串，但请记住v，y不要太远p（根据条件 1）。
你没有任何选择v ，y这样你就可以用语言生成新的字符串！
（第 1 步）：因为如果您选择增加，1那么您不能同时泵送 RHS 和 LHS 的两侧，=因为 LHS 上的最后一个1位于q(>p) 到1RHS 的第一个。因此不可能用语言生成新的字符串。
（步骤 2）：假设您想0再次抽水，它不可能同时增加0LHS 和 RHS，因为0m-1 (>p) 中的 LHS 上的最后一个膨胀到0RHS 上的第一个。
（第 3 步）：您不能同时泵送111...000... 两侧。，试试这个，你会得到语言 L 的字符串。
在 Pumping Lemma 的规则内尝试其他选项。你不会为vand找到正确的选择y。
[回答]
所以他s在 L 中有一个足够大的字符串，使用它我们不能用语言生成新的字符串。它与 Pumping Lemma for CFL 相矛盾，因此给出L的不是 CFL。