GATE CSE 2019 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2019

MCQ (Single Correct Answer)

-0.33

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

Suffix (L) = {y ∈ Σ* such that xy ∈ L}

{ww^R │w ∈ L}

Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}

L ∙ L^R = {xy │ x ∈ L, y^R ∈ L}

GATE CSE 2019

MCQ (Single Correct Answer)

-0.67

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

$\left\{w w^R \mid w \in\{a, b\}^*\right\}$

$\left\{w a^n b^n w^R \mid w \in\{a, b\}^*, n \geq 0\right\}$

$\left\{w a^n w^R b^n \mid w \in\{a, b\}^*, n \geq 0\right\}$

$\left\{a^n b^i \mid i \in\{n, 3 n, 5 n\}, n \geq 0\right\}$

GATE CSE 2019

MCQ (Single Correct Answer)

-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?

S1 and S2

S3 and S4

S2 and S3

S1 and S4

GATE CSE 2019

Numerical

-0

Let $\Sigma$ be the set of all bijections from $\{1, \ldots, 5\}$ to $\{1, \ldots, 5\}$, where id denotes the identity function, i.e. $\operatorname{id}(j)=j, \forall j$. Let $\circ$ denote composition on functions. For a string $x=$ $x_1 x_2 \cdots x_n \in \Sigma^n, n \geq 0$, let $\pi(x)=x_1 \circ x_2 \circ \cdots \circ x_n$. Consider the language $L=\left\{x \in \Sigma^* \mid \pi(x)=i d\right\}$. The minimum number of states in any DFA accepting $L$ is $\qquad$

Your input ____

PREVIOUS NEXT

GATE CSE Papers

2025