我在这方面考虑了很长时间，但仍然无法在这方面走得太远。第一步很容易考虑任何形式为 o^M 的语言，其中 M 是大于我们对手给出的素数（假设是 n）。我无法弄清楚我们如何从这里证明无论我们的对手如何打破字符串，我们总是可以泵送它以表明它不属于上下文无关语言类（因此不属于常规语言）。
PS：这不是作业问题。我已经完成了这门课程。只是想解决它，因为我在课程期间无法解决它。
问问题
2325 次
1 回答
1
假设给定的语言是上下文无关的。使用上下文无关语言的泵引理，您将得到数字 x 和 y，使得 x、x+y、x+2y、x+3y 等都是素数。然而，这是不可能的，因为素数之间存在任意大的差距（为了证明这一点，考虑数字 n！+2，n！+3，...。n！+ n，对于任何自然数 n>= 2 - 它们都是复合的）。
另一种方法是使用定理，即在一元字母表上的每种上下文无关语言都是常规语言。然后考虑一元字母表上的 DFA 看起来如何：每个状态都有一个输出边。消除不可达状态后，状态必须是 q_0, q_1, ... q_k，其中从 q_i 到 q_{i+1} 的转移，对于 1 <= i < k，从 q_k 转移到某个状态。q_0 是初始状态。无论选择的最终状态集如何，这都不能接受 { 0^n | n 是素数 } - 再次使用素数之间存在任意大间隙的事实来得到矛盾。
于 2011-12-06T16:02:54.077 回答