The GATE Grind

GATE 2017 CS (CS2) – Question 26

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple choice

With start S and rules S→XY, X→aX|a, Y→aYb|ε, identify the language.

  1. $\{a^mb^n:m\ge n,\ n>0\}$
  2. $\{a^mb^n:m\ge n,\ n\ge0\}$
  3. $\{a^mb^n:m>n,\ n\ge0\}$
  4. $\{a^mb^n:m>n,\ n>0\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\{a^mb^n:m>n,\ n\ge0\}$

Explanation

X produces aᵏ with k≥1. Y produces aⁿbⁿ with n≥0. Their concatenation is aᵏ⁺ⁿbⁿ, so the a exponent is strictly larger than n, while n can be zero. Conversely any m>n≥0 is obtained with k=m−n. Thus C.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →