GATE 2017 CS 组 1

答案： B

说明

在上面的表格中，我们可以看到：T(Q1) 和 D(Q0) 在第 3 个周期后是 11，在第 4 个周期后是 01。因此，选项 (B) 是正确的答案。

答案： D

说明

给定语法，
   S->aSb | bSa | SS | ∈
上面的语法将始终产生相等数量的 a 和 b。现在我们可以使用以下产生式序列生成给定的选项

对于选项 a
   S->aSb->abSab->abab

对于选项 b
   S->aSb->aSaSb->aSaSab->aaab

对于选项 c
   S->SS->aSbSaS->abbSaa->abbaa

对于选项 d
   它产生的 b 的数量多于 a，这肯定不能由此语法生成。

因此，选项(D)是正确答案。

答案： A

说明

所以，输出 fun1(5) = 53423122233445。因此选项(A)是正确的答案。

答案：C

说明

首先，取 foo 函数，根据问题，变量 val 的初始值为 3。现在当 foo(val--) 被调用时，它返回 val = 2，然后，它一次又一次地调用 foo(3)，而 foo(3) 又调用 foo(3)，以此类推。所以，在这里我们可以看到 foo(3) 被调用了无限次，这会导致突然终止。

现在，我们考虑一个 bar。在这个例子中，我们可以看到循环中 val 没有递减。所以当 bar(int val) 被调用时，它的执行如下，
   bar(3) 将调用 bar(2)
   bar(2) 将调用 bar(1)
   bar(1) 将调用 bar(0)→ 这里，bar(0) 返回 0
   bar(1) 将调用 bar(0)

所以在这里我们可以看到有一个无限循环的问题，但它不会被突然终止。

因此，选项 (C) 是正确答案。

答案： B

说明

语法 G1 生成的语言是，
   L(G1) = aⁿc^∗bⁿ | n≥0

语法 G2 生成的语言是，
   L(G2) = bⁿc^∗aⁿ | n≥0

两种语言的交集将是，
   L(G1)∩L(G2) = c∗

我们知道 c* 是一种正则语言，并且是无限的。因此选项 (B) 将是正确的答案。

答案： A

说明

已知,
L₁ = {aⁿbⁿc^m | m, n >= 0} 和
L₂ = {a^mbⁿcⁿ| m, n >= 0}

我们知道上下文无关语言的并集也是上下文无关语言。

所以，L3 = L1 ∪ L2 = { aⁿbⁿc^m ∪ a^mbⁿcⁿ | n, m >= 0 } 也是上下文无关语言。

由于在 L1 中：a 的数量 = b 的数量，而在 L2 中：b 的数量 = c 的数量。因此，它们的并集也是一种上下文无关语言。所以这是真的。

上下文无关语言的交集可能也是上下文无关语言，也可能不是。

L3 = L1 ∩ L2 = {aⁿbⁿcⁿ| n >= 0} 不能是上下文无关语言。

因此，选项 (A) 将是正确答案。

答案： A

说明

根据图灵机的定义，即，每个递归语言都是可计算的，但反过来可能不成立。

因此，选项 (A) 将是正确答案。

答案： B

说明

根据规则，当页面替换算法不是堆栈算法时，它会受到 Belady 异常的影响。堆栈算法是满足包含属性的算法。包含属性是 k 帧内存中的页面集始终是 (k + 1) 帧内存中的页面集的子集。

在语句 S1 中：随机页面替换算法可以选择以 FIFO 方式或不满足包含属性的方式替换页面。所以，它可能受到 Belady 异常的影响。

在语句 S2 中：LRU 是一种堆栈算法。所以，它不会受到 Belady 异常的影响。

因此，选项(B)是正确答案。