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

# PDA for aⁿb^(3n)

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2071 Chaitra
- Video: [Theory of Computation: PDA Example (a^n b^2n)](https://www.youtube.com/watch?v=K_kYGkeP3L8) — Anita R
- 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-b3n
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Design a PDA that accepts the language L = {aⁿb^(3n) : n ≥ 1}. Test your design for the string abbb. [Printed test string reads "aabbb" in the scan, but the worked trace uses abbb.]

## Short answer

The PDA pushes three A's for each a, then pops one A per b. For abbb, it pushes AAA, then pops three A's, reaching the final state with empty stack, so it is accepted.

## Answer

**Idea:** for each a read, push **three** A's. Then for every b, pop one A. Accept when the stack is back to Z0.

M = ({q0, q1, qf}, {a, b}, {A, Z0}, δ, q0, Z0, {qf})

| # | Transition | Meaning |
|---|---|---|
| 1 | δ(q0, a, Z0) = {(q0, AAAZ0)} | first a: push 3 A's |
| 2 | δ(q0, a, A) = {(q0, AAAA)} | each further a: push 3 more |
| 3 | δ(q0, b, A) = {(q1, ε)} | first b: pop one A |
| 4 | δ(q1, b, A) = {(q1, ε)} | each b pops one A |
| 5 | δ(q1, ε, Z0) = {(qf, Z0)} | stack empty: accept |

```text
  a,Z0/AAAZ0                 b,A/ε
  a,A/AAAA                    ↺
     ↺          b,A/ε
 ──► (q0) ─────────────► (q1) ──ε,Z0/Z0──► ((qf))
```

Because rules 3 and 4 are the only moves on b and no move on a exists in q1, all a's come before all b's. Since n ≥ 1, at least one a is read, so the string cannot be empty.

#### Test for abbb (n = 1)
```text
(q0, abbb, Z0)
⊢ (q0, bbb, AAAZ0)   push 3 A's for a
⊢ (q1, bb,  AAZ0)    b: pop
⊢ (q1, b,   AZ0)     b: pop
⊢ (q1, ε,   Z0)      b: pop
⊢ (qf, ε,   Z0)      accept
```
**abbb is accepted.** (The printed string aabbb has 2 a's but only 3 b's; it needs 6 b's, so the machine gets stuck with AAA on the stack and rejects it, which is correct since aabbb ∉ L.)

## Check yourself

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

1. How does the PDA for aⁿb³ⁿ work?
   A. Pushes one A per a and pops three per b
   B. Pushes three A's per a and pops one A per b
   C. Pushes B for each b
   D. Uses no stack
   Answer: B. For each a it pushes three A's; each b then pops one. (Key point: Strategy)

2. When does the PDA move to the final state qf?
   A. When the input starts
   B. When any b is read
   C. When the stack is back to Z0 after the b's
   D. When an a is read in q1
   Answer: C. The ε,Z0/Z0 move from q1 is possible only when all A's are popped. (Key point: Acceptance)

3. How does the PDA ensure all a's come before all b's?
   A. It has no move on a in state q1
   B. It uses two stacks
   C. It pops Z0 early
   D. It reads b's first
   Answer: A. Once in q1 (after a b), there is no a-transition, so a later a makes it stuck. (Key point: Ordering a before b)

4. After reading a in abbb, what is the stack?
   A. A Z0
   B. AAAZ0
   C. AAAAZ0
   D. Z0
   Answer: B. One a pushes three A's: AAAZ0, which three b's then pop. (Key point: Test of abbb)

## Related in Theory of Computation

- [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^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
- [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
- [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
- [Insulator discs per string, 180 MW over 200 km](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Ainsulator-discs-180mw-200km) — Transmission and Distribution System Design, chapter 3