---
title: "Grammar for aⁿbⁿcⁿ, n ≥ 1"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:grammar-an-bn-cn"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/grammar-an-bn-cn
site: BCT Engineering
---

# Grammar for aⁿbⁿcⁿ, n ≥ 1

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2072 Kartik
- Video: [Context Sensitive Grammar and Language || Lesson 79 || Finite Automata || Learning Monkey ||](https://www.youtube.com/watch?v=-NIU0dJRmUE) — Wisdomers - Computer Science and Engineering 
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/grammar-an-bn-cn
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Construct a grammar to accept the language L = {aⁿbⁿcⁿ : n ≥ 1}.

## Short answer

The language is not context-free; use a context-sensitive grammar. S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc.

## Answer

L = { aⁿbⁿcⁿ : n ≥ 1 } is not context free, so an unrestricted (context sensitive) grammar is needed. Here every production has |left side| ≤ |right side|.

#### Grammar
G = ({S, B, C}, {a, b, c}, P, S) with productions

```text
1. S  → aSBC
2. S  → aBC
3. CB → BC
4. aB → ab
5. bB → bb
6. bC → bc
7. cC → cc
```

**Idea.** Rules 1 and 2 generate n a's followed by n copies of B and C mixed together: aⁿ (BC)ⁿ. Rule 3 sorts them so that all B's come before all C's. Rules 4 to 7 convert the variables into terminals from left to right, and only in the correct order, so the result is always aⁿbⁿcⁿ.

#### Derivation of aabbcc (n = 2)
```text
S ⇒ aSBC            (1)
  ⇒ aaBCBC          (2)
  ⇒ aaBBCC          (3: CB → BC)
  ⇒ aabBCC          (4: aB → ab)
  ⇒ aabbCC          (5: bB → bb)
  ⇒ aabbcC          (6: bC → bc)
  ⇒ aabbcc          (7: cC → cc)
```

#### Why only aⁿbⁿcⁿ is generated
The first B can become b only when it follows an a (rule 4), each later B only after a b (rule 5), and C can become c only after b or c (rules 6 and 7). If a C is turned into c while a B still stands to its right, that B is stuck after a c (there is no rule cB → …), so the derivation can never reach a terminal string. Hence the variables must be sorted into B…BC…C before the conversion finishes. The numbers of a's, B's and C's are always equal, since rules 1 and 2 create them together.

## Check yourself

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

1. Why can't a CFG generate a^n b^n c^n?
   A. The language is not context free
   B. It is too short
   C. It is regular
   D. It has no terminals
   Answer: A. The pumping lemma shows it is not context free, so context-sensitive rules are needed. (Key point: Type)

2. What is the role of CB -> BC?
   A. Sorts so all B's come before all C's
   B. Converts B to b
   C. Adds a's
   D. Ends derivation
   Answer: A. Rules 1 and 2 give a^n (BC)^n; rule 3 sorts them into B^n C^n. (Key point: Sorting rule)

3. Why are the numbers of a, b, c equal?
   A. a, B and C are created together by S -> aSBC and S -> aBC
   B. The rules count them
   C. c is last
   D. By luck
   Answer: A. Each use of rule 1 or 2 adds exactly one a, one B, one C. (Key point: Equal counts)

4. Why are B and C converted only in order?
   A. Rules aB->ab, bB->bb, bC->bc, cC->cc need the correct left neighbour
   B. Any order works
   C. They are converted at random
   D. Only C can convert
   Answer: A. A B becomes b only after a or b, and C becomes c only after b or c, forcing sorted form. (Key point: Conversion)

## Related in Theory of Computation

- [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×
- [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×
- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — Theory of Computation, chapter 4
- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2
- [PDA for a^n b^(n+m) c^m](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-bm-cm-n-plus) — 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
- [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×
- [NFA and DFA from grammar σ→aA|bB](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-nfa-dfa-sigma-aa-bb) — Discrete Structure, chapter 2, asked 2×