GATE CS 2026 (Forenoon) — Question 52

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataMSQ2 marksMedium

Consider the following context-free grammar \( G \): \( S \rightarrow abaaBAbba \) \( A \rightarrow aaBBAb \mid bBabaa \) \( B \rightarrow aBb \mid 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 \( 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?
  1. A
    There is a string \( s \in L(G) \) such that \( n_1(s) < n_2(s) \)
  2. B
    For every string \( s \in L(G) \), \( n_1(s) \ge n_2(s) \)
  3. C
    There is a string \( s \in L(G) \) such that \( n_1(s) > 2n_2(s) \)
  4. D
    For every string \( s \in L(G) \), \( n_1(s) \le 2n_2(s) \)
Practise the full 2026-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Context-Free Grammars & Push-Down AutomataTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group