1
GATE CSE 2021 Set 1
Numerical
+2
-0

Consider the following ANSI C function:

int SimpleFunction (int y[], int n, int x)

{

int total = y[0], loopIndex;

for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)

total = x * total + y[loopIndex];

return total :

}

Let Z be an array of 10 elements with Z[i] = 1, for all i such that 0 ≤ i ≤ 9. The value returned by SimpleFunction (Z, 10, 2) is ______

Your input ____
2
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+1
-0.33
Suppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily context-free?
A
L1 ⋅ L2
B
L1 ∪ L2
C
L1 ∩ L2
D
L1 - L2
3
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.

L1 = {(M) | M takes more than 2021 steps on all inputs}

L2 = {(M) | M takes more than 2021 steps on some input}

Which one of the following options is correct?

A
Both L1 and L2 are undecidable.
B
L1 is undecidable and L2 is decidable.
C
L1 is decidable and L2 is undecidable.
D
Both L1 and L2 are decidable.
4
GATE CSE 2021 Set 1
Numerical
+2
-0

In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form,

GATE CSE 2021 Set 1 Theory of Computation - Push Down Automata and Context Free Language Question 16 English 1

where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X, Y ∈ Γ ∪ {ϵ}, represents

(q, Y) ∈ δ(p, a, X).

Consider the following pushdown automaton over the input alphabet ∑ = {a, b} and stack alphabet Γ = {#, A}.

GATE CSE 2021 Set 1 Theory of Computation - Push Down Automata and Context Free Language Question 16 English 2
The number of strings of length 100 accepted by the above pushdown automaton is ______

Your input ____
EXAM MAP