证明这些语言不是上下文无关的？
Prove that the languages are not context free?
如何证明以下语言不是上下文无关的？任何帮助将不胜感激。谢谢你。
大号 = {0^n| n 是素数}
反证法。假设语言是上下文无关的。然后，通过上下文无关语言的泵引理，L 中的任何字符串都可以写为 uvxyz，其中 |vxy| < p, |维| > 0 并且对于所有自然数 k，u(v^k)x(y^k)z 也在该语言中。选择 0^m，其中 m 是任何 > p 的素数。然后我们必须能够将 0^m 写成 uvxyz 以便 |vy| > 0. 让 |vy| = r。那么 0^(m-r+kr) 对任何自然数 k 一定是素数。然而，选择 k=m+1 给出 m-r+(m+1)r = m - r + mr + r = m(1 + r) 不能是素数，这是一个矛盾。因此，我们关于该语言是上下文无关的假设是不成立的。
如何证明以下语言不是上下文无关的？任何帮助将不胜感激。谢谢你。 大号 = {0^n| n 是素数}
反证法。假设语言是上下文无关的。然后，通过上下文无关语言的泵引理，L 中的任何字符串都可以写为 uvxyz，其中 |vxy| < p, |维| > 0 并且对于所有自然数 k，u(v^k)x(y^k)z 也在该语言中。选择 0^m，其中 m 是任何 > p 的素数。然后我们必须能够将 0^m 写成 uvxyz 以便 |vy| > 0. 让 |vy| = r。那么 0^(m-r+kr) 对任何自然数 k 一定是素数。然而，选择 k=m+1 给出 m-r+(m+1)r = m - r + mr + r = m(1 + r) 不能是素数，这是一个矛盾。因此，我们关于该语言是上下文无关的假设是不成立的。