Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2017
Hard
Identify the language generated by the following grammar, where S is the start variable.
S → XY X → aX | a Y → aYb | ε
- A{aᵐbⁿ | m ≥ n, n > 0}
- B{aᵐbⁿ | m ≥ n, n ≥ 0}
- {aᵐbⁿ | m > n, n ≥ 0}
- D{aᵐbⁿ | m > n, n > 0}
Explanation
X generates aᵏ for k ≥ 1. Y generates aⁿbⁿ for n ≥ 0 (including ε). So S = XY generates a^(k+n) b^n with k ≥ 1, n ≥ 0. Writing total a-count as m = k+n, since k ≥ 1, m = k+n ≥ n+1 > n. And n can be 0 (when Y=ε). So the language is exactly {aᵐbⁿ | m > n, n ≥ 0}.
Source: GATE CS 2017 (Session 2) (2017)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.