Crack
GATE
C
G
Topic
Context-free grammars and push-down automata
Theory of Computation
0
/ 17 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
1
1
0
0
2018
0
0
0
0
2019
0
0
0
0
2020
2
1
0
1
2021
0.5
0
0
0.5
2022
0
0
0
0
2023
1
1
0
0
2024
1
0
0.5
0.5
2025
2
2
0
0
2026
2
0
2
0
1
CS 2026 Set 1 · 1 mark · MSQ · Hard
Consider the following grammar where
S
S
S
is the start symbol, and
a
a
a
and
b
b
b
are terminal symbols.
2
CS 2026 Set 1 · 2 marks · MSQ · Hard
Consider the following context-free grammar
G
G
G
.
3
CS 2026 Set 2 · 1 mark · MSQ · Moderate
Which of the following grammars is/are ambiguous?
4
CS 2026 Set 2 · 2 marks · MSQ · Hard
Let
Σ
=
{
a
,
b
,
c
,
d
}
\Sigma = \{a, b, c, d\}
Σ
=
{
a
,
b
,
c
,
d
}
and let
L
=
{
a
i
b
j
c
k
d
ℓ
∣
i
,
j
,
k
,
ℓ
≥
0
}
L = \{a^i b^j c^k d^\ell \mid i, j, k, \ell \ge 0\}
L
=
{
a
i
b
j
c
k
d
ℓ
∣
i
,
j
,
k
,
ℓ
≥
0
}
.
5
CS 2025 Set 1 · 1 mark · MCQ · Easy
Consider the following context-free grammar
G
G
G
, where
S
S
S
,
A
A
A
, and
B
B
B
are the variables (non-terminals),
a
a
a
and
b
b
b
are the terminal symbols,
S
S
S
is the start variable, and the rules of
G
G
G
are described as:
6
CS 2025 Set 1 · 2 marks · MCQ · Moderate
Consider the following two languages over the alphabet
{
a
,
b
,
c
}
\{a, b, c\}
{
a
,
b
,
c
}
, where
m
m
m
and
n
n
n
are natural numbers.
7
CS 2025 Set 2 · 1 mark · MCQ · Easy
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
8
CS 2025 Set 2 · 1 mark · MCQ · Moderate
Let
G
1
,
G
2
G_1, G_2
G
1
,
G
2
be Context Free Grammars (CFGs) and
R
R
R
be a regular expression. For a grammar
G
G
G
, let
L
(
G
)
L(G)
L
(
G
)
denote the language generated by
G
G
G
.
9
CS 2024 Set 1 · 2 marks · NAT · Easy
Let
G
=
(
V
,
Σ
,
S
,
P
)
G = (V, \Sigma, S, P)
G
=
(
V
,
Σ
,
S
,
P
)
be a context-free grammar in Chomsky Normal Form with
Σ
=
{
a
,
b
,
c
}
\Sigma = \{a,b,c\}
Σ
=
{
a
,
b
,
c
}
and
V
V
V
containing 10 variable symbols including the start symbol
S
S
S
. The string
w
=
a
30
b
30
c
30
w = a^{30} b^{30} c^{30}
w
=
a
30
b
30
c
30
is derivable from
S
S
S
. The number of steps (application of rules) in the derivation
S
⇒
∗
w
S \Rightarrow^* w
S
⇒
∗
w
is ____
10
CS 2024 Set 2 · 2 marks · MSQ · Moderate
Consider a context-free grammar
G
G
G
with the following
3
3
3
rules.
11
CS 2023 · 2 marks · MCQ · Moderate
Consider the pushdown automaton (PDA)
P
P
P
below, which runs on the input alphabet
{
a
,
b
}
\{a,b\}
{
a
,
b
}
, has stack alphabet
{
⊥
,
A
}
\{\perp,A\}
{
⊥
,
A
}
, and has three states
{
s
,
p
,
q
}
\{s,p,q\}
{
s
,
p
,
q
}
, with
s
s
s
being the start state. A transition from state
u
u
u
to state
v
v
v
, labelled
c
/
X
/
γ
c/X/\gamma
c
/
X
/
γ
, where
c
c
c
is an input symbol or
ϵ
\epsilon
ϵ
,
X
X
X
is a stack symbol, and
γ
\gamma
γ
is a string of stack symbols, represents the fact that in state
u
u
u
, the PDA can read
c
c
c
from the input, with
X
X
X
on the top of its stack, pop
X
X
X
from the stack, push in the string
γ
\gamma
γ
on the stack, and go to state
v
v
v
. In the initial configuration, the stack has only the symbol
⊥
\perp
⊥
in it. The PDA accepts by empty stack.
12
CS 2021 Set 1 · 2 marks · NAT · Moderate
In a pushdown automaton
P
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
F
)
P = (Q, \Sigma, \Gamma, \delta, q_0, F)
P
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
F
)
, a transition of the form.
13
CS 2020 · 1 mark · MCQ · Hard
Consider the language
L
=
{
a
n
∣
n
≥
0
}
∪
{
a
n
b
n
∣
n
≥
0
}
L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}
L
=
{
a
n
∣
n
≥
0
}
∪
{
a
n
b
n
∣
n
≥
0
}
and the following statements.
14
CS 2020 · 1 mark · NAT · Moderate
Consider the following grammar.
15
CS 2015 Set 1 · 1 mark · MCQ · Moderate
For any two languages
L
1
L_1
L
1
and
L
2
L_2
L
2
such that
L
1
L_1
L
1
is context-free and
L
2
L_2
L
2
is recursively enumerable but not recursive, which of the following is/are necessarily true?
16
CS 2015 Set 1 · 2 marks · MCQ · Moderate
Consider the NPDA
(
Q
=
{
q
0
,
q
1
,
q
2
}
,
Σ
=
{
0
,
1
}
,
Γ
=
{
0
,
1
,
⊥
}
,
δ
,
q
0
,
⊥
,
F
=
{
q
2
}
)
(Q = \{q_0, q_1, q_2\}, \Sigma = \{0, 1\}, \Gamma = \{0, 1, \perp\}, \delta, q_0, \perp, F = \{q_2\})
(
Q
=
{
q
0
,
q
1
,
q
2
}
,
Σ
=
{
0
,
1
}
,
Γ
=
{
0
,
1
,
⊥
}
,
δ
,
q
0
,
⊥
,
F
=
{
q
2
})
, where (as per usual convention)
Q
Q
Q
is the set of states,
Σ
\Sigma
Σ
is the input alphabet,
Γ
\Gamma
Γ
is the stack alphabet,
δ
\delta
δ
is the state transition function,
q
0
q_0
q
0
is the initial state,
⊥
\perp
⊥
is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:
17
CS 2015 Set 3 · 2 marks · MCQ · Moderate
Which of the following languages are context-free?