Project ForgeConsider the following context-free grammars:
G1: S → aS | B, B → b | bB G2: S → aA | bB, A → aA | B | ε, B → bB | ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
- A{aᵐbⁿ|m>0 or n>0} and {aᵐbⁿ|m>0 and n>0}
- B{aᵐbⁿ|m>0 and n>0} and {aᵐbⁿ|m>0 or n≥0}
- C{aᵐbⁿ|m≥0 or n>0} and {aᵐbⁿ|m>0 and n>0}
- {aᵐbⁿ|m≥0 and n>0} and {aᵐbⁿ|m>0 or n>0}
Explanation
G1: S generates any number (≥0) of a's via aS, then B forces at least one b (B→b|bB never allows zero b's) — giving {aᵐbⁿ|m≥0 and n>0}. G2: branch S→bB gives 0 a's and n≥1 b's (via b then B→bB|ε allowing n≥1 total); branch S→aA gives m≥1 a's (via aA) then either ε (n=0) or B (n≥0 via bB|ε) — giving m≥1,n≥0. The union of both branches excludes only the single case m=0,n=0 (empty string, never reachable since S always starts with a or b) — giving {aᵐbⁿ|m>0 or n>0}.
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.