1
GATE CSE 2019
MCQ (Single Correct Answer)
+1
-0.33
For Σ = {a, b}, let us consider the regular language L = {x | x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A
9
B
5
C
24
D
3
2
GATE CSE 2019
MCQ (Single Correct Answer)
+1
-0.33
If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?
A
Suffix (L) = {y ∈ Σ* such that xy ∈ L}
B
{wwR │w ∈ L}
C
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}
D
L ∙ LR = {xy │ x ∈ L, yR ∈ L}
3
GATE CSE 2019
MCQ (Single Correct Answer)
+2
-0.67

Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?

A
$\left\{w w^R \mid w \in\{a, b\}^*\right\}$
B
$\left\{w a^n b^n w^R \mid w \in\{a, b\}^*, n \geq 0\right\}$
C
$\left\{w a^n w^R b^n \mid w \in\{a, b\}^*, n \geq 0\right\}$
D
$\left\{a^n b^i \mid i \in\{n, 3 n, 5 n\}, n \geq 0\right\}$
4
GATE CSE 2019
MCQ (Single Correct Answer)
+2
-0.67

Consider the following sets :

S1. Set of all recursively enumerable languages over the alphabet $\{0,1\}$

S2. Set of all syntactically valid C programs

S3. Set of all languages over the alphabet $\{0,1\}$

S4. Set of all non-regular languages over the alphabet $\{0,1\}$

Which of the above sets are uncountable?

A
S1 and S2
B
S3 and S4
C
S2 and S3
D
S1 and S4
EXAM MAP