Crack
GATE
C
G
Topic
Regular and context-free languages
Theory of Computation
0
/ 18 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
3
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
0.3
0.3
0
0
2018
0
0
0
0
2019
2
2
0
0
2020
2
2
0
0
2021
2
1
1
0
2022
3
0
3
0
2023
2
1
1
0
2024
0.5
0
0.5
0
2025
1
0.5
0.5
0
2026
0.5
0
0.5
0
1
CS 2026 Set 1 · 2 marks · MSQ · Moderate
Let
L
1
L_1
L
1
and
L
2
L_2
L
2
be two languages over a finite alphabet, such that
L
1
∩
L
2
L_1 \cap L_2
L
1
∩
L
2
and
L
2
L_2
L
2
are regular languages.
2
CS 2025 Set 1 · 2 marks · MCQ · Hard
Consider the following two languages over the alphabet {a, b}:
3
CS 2025 Set 2 · 1 mark · MSQ · Moderate
Consider the two lists
List I
and
List II
given below:
4
CS 2024 Set 1 · 1 mark · MSQ · Moderate
Let
L
1
,
L
2
L_1, L_2
L
1
,
L
2
be two regular languages and
L
3
L_3
L
3
a language which is not regular. Which of the following statements is/are always TRUE?
5
CS 2023 · 1 mark · MSQ · Moderate
Which of the following statements is/are CORRECT?
6
CS 2023 · 2 marks · MCQ · Moderate
Consider the context-free grammar
G
G
G
below
7
CS 2022 · 1 mark · MSQ · Moderate
Which of the following statements is/are TRUE?
8
CS 2022 · 2 marks · MSQ · Hard
Consider the following languages:
9
CS 2022 · 2 marks · MSQ · Hard
Consider the following languages:
10
CS 2021 Set 1 · 1 mark · MCQ · Easy
Suppose that
L
1
L_1
L
1
is a regular language and
L
2
L_2
L
2
is a context-free language. Which one of the following languages is NOT necessarily context-free?
11
CS 2021 Set 2 · 1 mark · MSQ · Hard
Let
L
1
L_1
L
1
be a regular language and
L
2
L_2
L
2
be a context-free language. Which of the following languages is/are context-free?
12
CS 2021 Set 2 · 2 marks · MCQ · Hard
Consider the following two statements about regular languages:
13
CS 2021 Set 2 · 2 marks · MSQ · Hard
For a string
w
w
w
, we define
w
R
w^R
w
R
to be the reverse of
w
w
w
. For example, if
w
=
01101
w = 01101
w
=
01101
then
w
R
=
10110
w^R = 10110
w
R
=
10110
.
14
CS 2020 · 1 mark · MCQ · Moderate
Consider the following statements.
15
CS 2020 · 2 marks · MCQ · Hard
Consider the following languages.
16
CS 2019 · 1 mark · MCQ · Hard
For
Σ
=
{
a
,
b
}
\Sigma = \{a, b\}
Σ
=
{
a
,
b
}
, let us consider the regular language
L
=
{
x
∣
x
=
a
2
+
3
k
or
x
=
b
10
+
12
k
,
k
≥
0
}
L = \{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k}, k \ge 0\}
L
=
{
x
∣
x
=
a
2
+
3
k
or
x
=
b
10
+
12
k
,
k
≥
0
}
. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for
L
L
L
?
17
CS 2019 · 2 marks · MCQ · Hard
Which one of the following languages over
Σ
=
{
a
,
b
}
\Sigma = \{a, b\}
Σ
=
{
a
,
b
}
is NOT context-free?
18
CS 2015 Set 2 · 2 marks · MCQ · Moderate
L
2
:
{
a
n
b
m
∣
m
≠
n
and
m
,
n
≥
0
}
L_2: \{a^n b^m \mid m \neq n \text{ and } m, n \geq 0\}
L
2
:
{
a
n
b
m
∣
m
=
n
and
m
,
n
≥
0
}
L
3
:
{
a
p
b
q
c
r
∣
p
,
q
,
r
≥
0
}
L_3: \{a^p b^q c^r \mid p, q, r \geq 0\}
L
3
:
{
a
p
b
q
c
r
∣
p
,
q
,
r
≥
0
}