The GATE Grind

GATE 2017 CS – Question 44

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

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. $abab$
  2. $aaab$
  3. $abbaa$
  4. $babba$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $babba$

Explanation

Every production adds at least as many $a$'s as $b$'s, and $SaS$ adds an $a$ with no $b$. So every string generated has at least as many $a$'s as $b$'s. The string $babba$ has 3 $b$'s and only 2 $a$'s, so it cannot be generated.