---
title: "CFG for aᵐbⁿ with m ≥ n"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-am-bn-m-ge-n"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-am-bn-m-ge-n
site: BCT Engineering
---

# CFG for aᵐbⁿ with m ≥ n

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2071 Chaitra
- Video: [Construction of CFG for the given language Examples - part 3 || TOC || Theory of Computation|| FLAT](https://www.youtube.com/watch?v=kbyXZmCfrGk) — Sudhakar Atchala
- 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-am-bn-m-ge-n
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Construct a CFG for the language L(G) = {aᵐbⁿ : m, n > 0, m ≥ n}. Use the grammar to generate the string "aaab". Also draw the parse tree.

## Short answer

Grammar: S → aSb | aS | ab. Derivation for aaab: S ⇒ aS ⇒ aaS ⇒ aaab. Parse tree: root S with children a, S; that S with a, S; that S with a, b (leaves a a a b).

## Answer

L = { aᵐbⁿ : m ≥ n ≥ 1 }. Each b is matched with an a, and the extra a's (m − n of them) can be placed anywhere on the left, because all the a's come first.

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

```text
S → aSb | aS | ab
```

- S → aSb adds one matched a…b pair.
- S → aS adds an extra a (so m can exceed n).
- S → ab ends the derivation with the last pair, ensuring n ≥ 1.

Every string is of the form aᵐbⁿ with m ≥ n ≥ 1: only a's are added on the left and b's on the right, and each b is created together with an a.

#### Derivation of aaab (m = 3, n = 1)
S ⇒ aS ⇒ aaS ⇒ aaab

The rules used are S → aS twice, then S → ab.

#### Parse tree
```text
            S
          / |
         a  S
          / |
         a  S
           / \
          a   b
```
Reading the leaves from left to right gives a, a, a, b = **aaab**. Each interior node is labelled S, and the bottom S uses S → ab.

## Check yourself

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

1. What does S → aSb do?
   A. Adds a matched a...b pair
   B. Adds an extra a only
   C. Ends the derivation
   D. Adds an extra b
   Answer: A. It places an a on the left and a b on the right, preserving m ≥ n. (Key point: Rule S → aSb)

2. What does S → aS achieve?
   A. Ensures n ≥ 1
   B. Adds an extra a without a matching b, allowing m > n
   C. Adds a b
   D. Matches pairs
   Answer: B. Extra a's let m exceed n. (Key point: Rule S → aS)

3. Why is S → ab the terminating rule instead of S → ε?
   A. To generate the empty string
   B. To make n ≥ 1 (at least one b and one a)
   C. To allow m < n
   D. To allow only m = n
   Answer: B. S → ab ensures at least one pair, which gives m, n ≥ 1. (Key point: Why S → ab)

4. Which derivation produces aaab?
   A. S ⇒ aSb ⇒ aaab
   B. S ⇒ aS ⇒ aaS ⇒ aaab
   C. S ⇒ aSb ⇒ aabb
   D. S ⇒ ab ⇒ aaab
   Answer: B. Use S → aS twice, then S → ab; this gives a·a·ab = aaab (m = 3, n = 1). (Key point: Derivation of aaab)

## Close variants set in other exams

- [CFG for aⁿb^(2n); parse tree](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-an-b2n-parse-tree) — 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

## 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
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2