GATEverse Practice, past papers & mock tests
GATE 2027: 115 days Sign in Create account
GATE 2026 · CS1 - Forenoon
Theory of ComputationPush Down Automata: CFL & DCFLhardMSQ2 marks
Consider the following context-free grammar G. S → abaABAbba A → aaBBAb | bBabaa B → aBb | ab 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 n1(s) be the number of a's in s and n2(s) be the number of b's in s. Which of the following statements is/are true?

Select every correct option.

Save your progress

Related Theory of Computation PYQs

GATE 2026 · CS1 - Forenoon

Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S → aSbS | bS | ε Which of the follo…

GATE 2026 · CS1 - Forenoon

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be …

GATE 2026 · CS1 - Forenoon

Let L1 and L2 be two languages over a finite alphabet, such that L1 intersect L2 and L2 are regular languages. Which of the follow…

GATE 2026 · CS2 - Afternoon

Which one of the following statements is equivalent to the following assertion? Turing machine M decides the language L subset of …

GATE 2026 · CS2 - Afternoon

Which of the following grammars is/are ambiguous?

GATE 2026 · CS2 - Afternoon

Let Σ = {a,b,c,d} and let L = {\(a^{i}\) \(b^{j}\) \(c^{k}\) \(d^{l}\) | i,j,k,l ≥ 0}. Which of the following constraints ensure(s…