GATE CS 2017 (Forenoon) — Question 34

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataMCQ2 marks · −2/3 if wrongMedium

If \(G\) is a grammar with productions \(S \rightarrow SaS \mid aSb \mid bSa \mid SS \mid \epsilon\) where \(S\) is the start variable, then which one of the following strings is not generated by \(G\)?
  1. A
    \(abab\)
  2. B
    \(aaab\)
  3. C
    \(abbaa\)
  4. D
    \(babba\)
Practise the full 2017-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