---
title: "PDA for a^n b^(n+m) c^m"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:pda-an-bm-cm-n-plus"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-an-bm-cm-n-plus
site: BCT Engineering
---

# PDA for a^n b^(n+m) c^m

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Shrawan
- Video: [Pushdown Automata (PDA) for aᵐ⁺ⁿbⁿcᵐ, aⁿbᵐ⁺ⁿcᵐ, aⁿbᵐcᵐ⁺ⁿ  || TOC || Automata Theory](https://www.youtube.com/watch?v=5D8GWplAK3E) — THE GATEHUB
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-an-bm-cm-n-plus
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Construct a PDA which accepts the language L = {aⁿ b^(n+m) c^m : n, m ≥ 1}. Verify your design for abbbcc.

## Short answer

Push A for each a. On b's, pop A until Z0 shows, then push B for extra b's. Pop B for each c. Accept on empty stack except Z0. The string abbbcc is accepted.

## Answer

L = { aⁿ b^(n+m) cᵐ : n, m ≥ 1 }. Write the b's as bⁿ·bᵐ: the first n b's match the a's, and the remaining m b's match the c's.

**Idea**
1. Push A for every a.
2. On b's, pop one A per b (matching a's).
3. When the A's are finished (Z0 on top), further b's push B.
4. On c's, pop one B per c. Accept when only Z0 is left.

M = ({q0, q1, q2, q3, qf}, {a, b, c}, {A, B, Z0}, δ, q0, Z0, {qf})

| # | Transition | Meaning |
|---|---|---|
| 1 | δ(q0, a, Z0) = {(q0, AZ0)} | push A |
| 2 | δ(q0, a, A) = {(q0, AA)} | push A |
| 3 | δ(q0, b, A) = {(q1, ε)} | first b pops an A |
| 4 | δ(q1, b, A) = {(q1, ε)} | b matches a |
| 5 | δ(q1, b, Z0) = {(q2, BZ0)} | a's used up: extra b, push B |
| 6 | δ(q2, b, B) = {(q2, BB)} | more extra b's |
| 7 | δ(q2, c, B) = {(q3, ε)} | first c pops a B |
| 8 | δ(q3, c, B) = {(q3, ε)} | c matches extra b |
| 9 | δ(q3, ε, Z0) = {(qf, Z0)} | accept |

```text
 a: push A      b,A/ε       b,Z0/BZ0      c,B/ε       ε,Z0/Z0
 ─► (q0) ──────► (q1) ────────► (q2) ───────► (q3) ────────► ((qf))
     ↺ a          ↺ b,A/ε        ↺ b,B/BB       ↺ c,B/ε
```
The requirement m ≥ 1 is enforced because acceptance is possible only after at least one c, which needs a B pushed by rule 5. If the a's are not all matched, A remains on the stack and Z0 is never exposed, so the string is rejected.

#### Verification for abbbcc (n = 1, m = 2)
```text
(q0, abbbcc, Z0)
⊢ (q0, bbbcc, AZ0)    push A
⊢ (q1, bbcc,  Z0)     b pops A
⊢ (q2, bcc,   BZ0)    b, Z0 on top: push B
⊢ (q2, cc,    BBZ0)   b: push B
⊢ (q3, c,     BZ0)    c pops B
⊢ (q3, ε,     Z0)     c pops B
⊢ (qf, ε,     Z0)     accept
```
**abbbcc is accepted.**

## Check yourself

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

1. How is aⁿb^(n+m)cᵐ understood?
   A. The first n b's match the a's, the remaining m b's match the c's
   B. All b's match the c's
   C. The a's match the c's
   D. Every b is matched with an a and a c
   Answer: A. Writing b^(n+m) as bⁿ·bᵐ lets one stack handle both comparisons in turn. (Key point: Decomposing the language)

2. When does the PDA start pushing B for b's?
   A. On the first b
   B. After reading a c
   C. When Z0 is on top because all A's are used up
   D. Never; it pushes only A
   Answer: C. Once the a's are matched, Z0 is exposed and extra b's push B. (Key point: Switch to pushing B)

3. How is m ≥ 1 enforced?
   A. By the final state being q0
   B. By requiring acceptance only after at least one c, which needs a B pushed
   C. By the alphabet
   D. By a counter in the state
   Answer: B. Reaching q3 needs a c popping a B, so at least one extra b must have been read. (Key point: Why m ≥ 1)

4. What happens if the b's don't remove all the A's?
   A. The string is accepted
   B. The stack gets B's
   C. A remains, Z0 is never exposed and the string is rejected
   D. The c's pop A
   Answer: C. Acceptance needs Z0 on top, which cannot occur if A's remain. (Key point: Rejecting unmatched a's)

## Related in Theory of Computation

- [PDA for aⁿb^(3n)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b3n) — Theory of Computation, chapter 3
- [PDA configuration; PDA for a^(3n)b^n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-config-a3n-bn) — Theory of Computation, chapter 3
- [PDA for aⁱbʲcᵏ with i = j + k](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-i-equals-j-plus-k) — Theory of Computation, chapter 3
- [PDA for aⁿb^(2n+1)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b2n-plus-1) — Theory of Computation, chapter 3
- [PDA for palindromes over {a,b}](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-palindrome-ab) — Theory of Computation, chapter 3
- [PDA for wwᴿ; accept abbbba](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-wwr-abbbba) — Theory of Computation, chapter 3

## Related in other subjects

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