1
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.
2
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$

3
GATE CSE 2024 Set 1
Numerical
+2
-0

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = { a, b, c } and V containing 10 variable symbols including the start symbol S. The string w = a30b30c30 is derivable from S. The number of steps (application of rules) in the derivation S ⟹ w is _______

Your input ____
4
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the context-free grammar G below

$$\matrix{ S & \to & {aSb|X} \cr X & \to & {aX|Xb|a|b,} \cr } $$

where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.

Which one of the following statements is CORRECT?

A
The language generated by G is $$(a+b)^*$$
B
The language generated by G is $$a^*(a+b)b^*$$
C
The language generated by G is $$a^*b^*(a+b)$$
D
The language generated by G is not a regular language
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP