Skip to main content

CFG for aⁿb^(2n); parse tree

Short answer

Grammar: S → aSbb | abb. Derivation for aabbbb: S ⇒ aSbb ⇒ aabbbb. Parse tree: root S → aSbb (children a, S, b, b); inner S → abb (children a, b, b). Leaves: a a b b b b.

Construct a CFG for the language L = {aⁿb^(2n), n > 0} and use this grammar to generate the string aabbbb. Also construct the parse tree.

L = { aⁿb²ⁿ : n > 0 }. Each a is matched with two b's.

Grammar

G = ({S}, {a, b}, P, S) with

S → aSbb | abb
  • S → aSbb adds one a on the left and two b's on the right.
  • S → abb ends the derivation with the innermost a and its two b's, so n ≥ 1.

By induction on n, S ⇒* aⁿb²ⁿ, and every derived terminal string has this form.

Derivation of aabbbb (n = 2)

S ⇒ aSbb ⇒ a(abb)bb = aabbbb (S → aSbb, then S → abb)

Parse tree

          S
       / / \ \
      a  S  b  b
       / | \
      a  b  b

The root S uses S → aSbb (children a, S, b, b). The inner S uses S → abb (children a, b, b). Leaves from left to right: a, a, b, b, b, b = aabbbb.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →