Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2016
Easy
Which of the following languages is generated by the given grammar? S → aS | bS | ε
- A{aⁿbᵐ | n,m ≥ 0}
- B{w∈{a,b}* | w has equal number of a's and b's}
- C{aⁿ|n≥0}∪{bⁿ|n≥0}∪{aⁿbⁿ|n≥0}
- {a,b}*
Explanation
S can expand via aS or bS any number of times, in any order, and terminate with ε at any point — this generates every possible string of a's and b's in any arrangement, i.e. the full Kleene closure {a,b}*.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
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.