登机门|登机门CS 2008 |问题8

以下哪项适用于该语言

（A） 图灵机器不接受它 （B） 它是常规的，但不是上下文无关的 （C） 它与上下文无关，但不规则 （D） 它既不是常规的，也不是上下文无关的，但被图灵机所接受 答复: （D） 说明： 图灵机可以设计为 ^P 使用“埃拉托斯坦筛”的概念。 假设给我们一个整数’n’，我们想找出所有小于或等于’n’的素数。

我们重复以下步骤： 我们找到列表中最小的数字，将其声明为素数，并从列表中删除该数字的所有倍数。我们一直这样做，直到每个元素都被声明为素数或从列表中删除。

现在，如果p=0或p=1，我们拒绝输入。 否则，我们将第一个和最后一个“a”替换为符号$。

在上面的步骤中，我们要做的是从左边找到第一个非黑色符号。让此符号出现在位置“x”处。假设“x”是一个质数。 如果此非空符号为$，则接受输入字符串。 但是，如果符号是“a”，我们将其标记为a*，并用符号“空白”替换所有“x”的倍数。 如果最后，符号$被替换为“blank”，我们将拒绝输入字符串（因为在这种情况下，p将是某些“x”的倍数）。 否则，我们返回并重复这些步骤。 因此，输入既不是规则的，也不是上下文无关的，而是被图灵机接受的。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验