1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+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 → ϵ
2
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 ______

3
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+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) = ∑*}
4
GATE CSE 2020
MCQ (Single Correct Answer)
+2
-0.67
Consider the following languages.

L1 = {wxyx | w, x, y ∈ (0 + 1)+}
L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?
A
L1 is regular and L2 is context-free.
B
L1 is context-free but not regular and L2 is context-free.
C
Neither L1 nor L2 is context-free.
D
L1 is context-free but L2 is not context-free.
GATE CSE Subjects
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12