1
GATE CSE 2026 Set 2
MCQ (More than One Correct Answer)
+2
-0

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$.

Which of the following constraints ensure(s) that the language $L$ is context-free?

A

$i+k=j+l$

B

$i=k$ and $j=l$

C

$i=l$ and $j=k$

D

$i+j=k+l$

2
GATE CSE 2026 Set 1
MCQ (More than One Correct Answer)
+2
-0

Consider the following context-free grammar $G$ :

$$ \begin{aligned} & S \rightarrow a b a A B A b b a \\ & A \rightarrow a a B B A b \mid b B a b a a \\ & B \rightarrow a B b \mid a b \end{aligned} $$

In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols.

Let $L(G)$ be the language generated by the grammar $G$. For a string $s \in L(G)$, let $n_1(s)$ be the number of a's in $s$ and $n_2(s)$ be the number of b's in $s$.

Which of the following statements is/are true?

A

There is a string $s \in L(G)$ such that $n_1(s)

B

For every string $s \in L(G), n_1(s) \geq n_2(s)$

C

There is a string $s \in L(G)$ such that $n_1(s)>2 n_2(s)$

D

For every string $s \in L(G), n_1(s) \leq 2 n_2(s)$

3
GATE CSE 2025 Set 1
MCQ (Single Correct Answer)
+2
-0

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers.

$$\begin{aligned} & L_1=\left\{a^m b^m c^{m+n} \mid m, n \geq 1\right\} \\ & L_2=\left\{a^m b^n c^{m+n} \mid m, n \geq 1\right\} \end{aligned}$$

Which ONE of the following statements is CORRECT?

A
Both $L_1$ and $L_2$ are context-free languages.
B
$L_1$ is a context-free language but $L_2$ is not a context-free language.
C
$L_1$ is not a context-free language but $L_2$ is a context-free language.
D
Neither $L_1$ nor $L_2$ are context-free languages.
4
GATE CSE 2024 Set 2
MCQ (More than One Correct Answer)
+2
-0

Consider a context-free grammar $G$ with the following 3 rules.

$S \rightarrow aS, \ S \rightarrow aSbS, S \rightarrow c$

Let $w \in L(G)$.

Let $n_a(w)$, $n_b(w)$, $n_c(w)$ denote the number of times $a$, $b$, $c$ occur in $w$, respectively. Which of the following statements is/are TRUE?

A

$n_a(w) > n_b(w)$

B

$n_a(w) > n_c(w) - 2$

C

$n_c(w) = n_b(w) + 1$

D

$n_c(w) = n_b(w) * 2$

GATE CSE Subjects

Browse all chapters by subject

Software Engineering
Web Technologies