---
title: "CFG for aⁿb^(2n); parse tree"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-an-b2n-parse-tree"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-an-b2n-parse-tree
site: BCT Engineering
---

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

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Shrawan
- Video: [Designing CFG for L = {a^n b^2n | n ≥ 0} and for L ={a^n b^2n | n ≥ 1}](https://www.youtube.com/watch?v=PtIo5Nyj76Y) — Lavina Jean Crasta
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-an-b2n-parse-tree
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

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.

## 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.

## Answer

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

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

```text
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
```text
          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**.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which grammar generates { a^n b^(2n) : n > 0 }?
   A. S -> aSb | ab
   B. S -> aSbb | abb
   C. S -> aabbS | abb
   D. S -> aSbb | epsilon
   Answer: B. Each a is paired with two b's: S -> aSbb adds one a and two b's, and S -> abb ends with n >= 1. (Key point: Grammar)

2. Why is the production S -> abb needed, and why not S -> epsilon?
   A. It ends the derivation with n = 1, since n > 0 excludes the empty string
   B. It allows n = 0
   C. It makes the grammar ambiguous
   D. It adds extra b's at the start
   Answer: A. The language requires n > 0, so the shortest string is abb; epsilon would wrongly add the empty string. (Key point: Base production)

3. What is the derivation of aabbbb?
   A. S => aSbb => aabbbb using S -> aSbb twice
   B. S => aSbb => a(abb)bb using S -> aSbb then S -> abb
   C. S => abb => aabbbb
   D. S => aSb => aabbbb
   Answer: B. n = 2 needs one application of S -> aSbb followed by S -> abb, giving a(abb)bb = aabbbb. (Key point: Derivation of aabbbb)

4. In the parse tree for aabbbb, what are the children of the root S?
   A. a, b, b
   B. a, a, b, b
   C. a, S, b, b
   D. S, b, b
   Answer: C. The root uses S -> aSbb, so its children are a, S, b, b; the inner S uses S -> abb. (Key point: Parse tree shape)

## Close variants set in other exams

- [CFG for aᵐbⁿ with m ≥ n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-am-bn-m-ge-n) — Theory of Computation, chapter 3, asked 2×

## Related in Theory of Computation

- [Role of parse tree in CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aparse-tree-role) — Theory of Computation, chapter 3
- [CFG for palindromes with parse trees](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-palindrome-parse-trees) — Theory of Computation, chapter 3
- [CFG versus unrestricted grammar](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-vs-unrestricted-grammar) — Theory of Computation, chapter 4
- [Unrestricted grammar; superset of CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aunrestricted-grammar-explain) — Theory of Computation, chapter 4, asked 2×
- [Ambiguity; language of S→SS|a](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aambiguity-inherent-ssa) — Theory of Computation, chapter 3
- [Define CFG with example](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-define-example) — Theory of Computation, chapter 3, asked 2×

## Related in other subjects

- [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2
- [Strictly binary tree has 2n-1 nodes](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astrict-binary-tree-nodes-proof) — Data Structure and Algorithm, chapter 6
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2
- [NFA and DFA from grammar σ→bσ|aC](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-bsigma-ac) — Discrete Structure, chapter 2, asked 4×