给定的语言是有效的 CFG 吗？
Is the given language a valid CFG?
语言，L = { a^n b^n a^n ; n=1,2,3,..}
我想检查给定的语言 L 是否是上下文无关的。
CFG 利用使用堆栈的PDA。因此，首先将每个 'a' 存储到堆栈中。然后每次弹出两次
'b' 的出现。这个逻辑对吗？
可以使用上下文无关语言的泵引理证明该语言不是上下文无关的。证明是反证法。假设语言是上下文无关的。那么语言中长度至少为 p 的词可以写成 uvxyz 和 |vxy| <= p, |维| > 0 并且其中 u(v^n)x(y^n)z 在所有整数 n 的语言中。选择语言中的字符串 a^p b^p a^p。有五种情况需要考虑：
vxy 仅由第一部分的 a 组成。向上或向下抽水打破了第一部分中 a 的数量等于第二部分中 b 的数量的要求。
vxy 仅由前两部分的 a 和 b 组成。泵送可能会保持第一部分中 a 的数量等于第二部分中 b 的数量的要求，但它肯定会打破第一部分和第三部分中 a 的数量相同的要求。
vxy 仅由第二部分的 b 组成。泵送失败的原因与案例 1 相同。
vxy 由第二部分和第三部分的 a 和 b 组成。泵送失败的原因与第二种情况类似。
vxy 仅由第三部分的 a 组成。泵送失败的原因与第一种情况类似。
因此，无法重写我们的字符串 a^n b^n a^n 使其可以写成 uvxyz 并满足泵引理的要求。这是一个矛盾，所以语言不可能是正则的。
语言，L = { a^n b^n a^n ; n=1,2,3,..}
我想检查给定的语言 L 是否是上下文无关的。
CFG 利用使用堆栈的PDA。因此，首先将每个 'a' 存储到堆栈中。然后每次弹出两次 'b' 的出现。这个逻辑对吗？
可以使用上下文无关语言的泵引理证明该语言不是上下文无关的。证明是反证法。假设语言是上下文无关的。那么语言中长度至少为 p 的词可以写成 uvxyz 和 |vxy| <= p, |维| > 0 并且其中 u(v^n)x(y^n)z 在所有整数 n 的语言中。选择语言中的字符串 a^p b^p a^p。有五种情况需要考虑：
vxy 仅由第一部分的 a 组成。向上或向下抽水打破了第一部分中 a 的数量等于第二部分中 b 的数量的要求。
vxy 仅由前两部分的 a 和 b 组成。泵送可能会保持第一部分中 a 的数量等于第二部分中 b 的数量的要求，但它肯定会打破第一部分和第三部分中 a 的数量相同的要求。
vxy 仅由第二部分的 b 组成。泵送失败的原因与案例 1 相同。
vxy 由第二部分和第三部分的 a 和 b 组成。泵送失败的原因与第二种情况类似。
vxy 仅由第三部分的 a 组成。泵送失败的原因与第一种情况类似。
因此，无法重写我们的字符串 a^n b^n a^n 使其可以写成 uvxyz 并满足泵引理的要求。这是一个矛盾，所以语言不可能是正则的。