1
GATE CSE 2021 Set 1
+2
-0.67
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
2
GATE CSE 2021 Set 1
+2
-0.67

Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}.

S → d a T | R f

T → a S | b a T | ϵ

R → c a T R | ϵ

The following is a partially-filled LL(1) parsing table.

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?

A
(1) S → R f (2) S → R f (3) T → ϵ (4) T → ϵ
B
(1) blank (2) S → R f (3) blank (4) blank
C
(1) S → R f (2) blank (3) blank (4) T → ϵ
D
(1) blank (2) S → R f (3) T → ϵ (4) T → ϵ
3
GATE CSE 2021 Set 1
Numerical
+2
-0.67

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

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}.

The number of strings of length 100 accepted by the above pushdown automaton is ______

4
GATE CSE 2021 Set 1
+2
-0.67
Let $$\left\langle M \right\rangle$$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?
A
L = { $$\left\langle M \right\rangle$$ | M is a PDA such that L(M) = ∑*}
B
L = { $$\left\langle M \right\rangle$$ | M is a DFA such that L(M) = Φ}
C
L = { $$\left\langle M \right\rangle$$ | M is a PDA such that L(M) = Φ}
D
L = { $$\left\langle M \right\rangle$$ | M is a DFA such that L(M) = ∑*}
GATE CSE Subjects
EXAM MAP
Medical
NEET