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

2
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 ____
3
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
4
GATE CSE 2023
MCQ (Single Correct Answer)
+2
-0.67

Consider the pushdown automation (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {$$\bot$$, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/$$\gamma$$, where c is an input symbol or $$\in $$, X is a stack symbol, and $$\gamma$$ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string $$\gamma$$ on the stack, and go to state v. In the initial configuration, the stack has only the symbol $$\bot$$ in it. The PDA accepts by empty stack.

GATE CSE 2023 Theory of Computation - Push Down Automata and Context Free Language Question 10 English

Which one of the following options correctly describes the language accepted by P?

A
$$\{ {a^m}{b^n}|1 \le m\,\mathrm{and}\,n < m\} $$
B
$$\{ {a^m}{b^n}|0 \le n \le m\} $$
C
$$\{ {a^m}{b^n}|0 \le m\,\mathrm{and}\,0 \le n\} $$
D
$$\{ {a^m}|0 \le m\} \cup \{ {b^n}|0 \le n\} $$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP