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

# PDA for aⁿb^(2n+1)

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2074 Asoj
- Video: [Construct PDA for the language L={a^n   b^2n} || Pushdown Automata || TOC || FLAT || Theory of Comp](https://www.youtube.com/watch?v=KXvl6QopXuc) — 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/pda-an-b2n-plus-1
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Design a PDA that accepts L = {aⁿb^(2n+1), n ≥ 0}. Check it for aabbbbb.

## Short answer

Push two A's per a. On first b, transition without popping (the +1). Then pop one A per remaining b. For aabbbbb, n=2 pushes 4 A's, skips one b, pops 4 A's, accepted.

## Answer

L = { aⁿ b^(2n+1) : n ≥ 0 }.

**Idea:** push two A's for each a. After the a's, read **one extra b without popping**, then pop one A for each remaining b. Accept when the stack shows Z0.

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

| # | Transition | Meaning |
|---|---|---|
| 1 | δ(q0, a, Z0) = {(q0, AAZ0)} | push 2 A's |
| 2 | δ(q0, a, A) = {(q0, AAA)} | push 2 more A's |
| 3 | δ(q0, b, Z0) = {(q1, Z0)} | the "+1" b (also case n = 0) |
| 4 | δ(q0, b, A) = {(q1, A)} | the "+1" b, stack unchanged |
| 5 | δ(q1, b, A) = {(q1, ε)} | each b pops one A |
| 6 | δ(q1, ε, Z0) = {(qf, Z0)} | accept |

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

For n = 0 the machine reads just "b": q0 → q1 → qf. For other strings the extra b is read once, then the number of remaining b's must equal 2n.

#### Check aabbbbb (n = 2, 5 b's)
```text
(q0, aabbbbb, Z0)
⊢ (q0, abbbbb, AAZ0)
⊢ (q0, bbbbb,  AAAAZ0)   after both a's: 4 A's
⊢ (q1, bbbb,   AAAAZ0)   extra b, no pop
⊢ (q1, bbb,    AAAZ0)
⊢ (q1, bb,     AAZ0)
⊢ (q1, b,      AZ0)
⊢ (q1, ε,      Z0)
⊢ (qf, ε,      Z0)       accept
```
**aabbbbb is accepted** (2 a's, 5 = 2·2 + 1 b's).

## 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^(2n+1) work?
   A. Pushes one A per a
   B. Pushes two A's per a, reads one extra b without popping, then pops one A per remaining b
   C. Pops two per b
   D. Reads the extra b first
   Answer: B. 2n b's need 2n A's, and the +1 b is read with the stack unchanged. (Key point: Strategy)

2. What does transition δ(q0, b, A) = (q1, A) do?
   A. Pops an A
   B. Pushes an A
   C. Reads the 'plus one' b without changing the stack
   D. Accepts the string
   Answer: C. It moves to q1 on the extra b while leaving the stack alone. (Key point: Extra b)

3. How is n = 0 (the string b) accepted?
   A. It is not accepted
   B. δ(q0, b, Z0) goes to q1 and then ε,Z0 to qf
   C. By popping Z0
   D. By reading a first
   Answer: B. With no a's the stack holds only Z0; reading b moves to q1, then the ε-move reaches qf. (Key point: Case n = 0)

4. For aabbbbb, how many A's are on the stack after reading both a's?
   A. 2
   B. 3
   C. 5
   D. 4
   Answer: D. Two A's per a gives 4 A's. (Key point: Stack after a's)

## 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ⁿb^(3n)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b3n) — 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 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

- [Journal bearing design with film thickness check](https://www.bctengineer.com/question.md?key=semester_6%2Fmachine_design_i%3Ajournal-bearing-minimum-film-thickness) — Machine Design I, chapter 7
- [Short note: check list methodology](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Ashort-note-checklist-design) — Information System, chapter 5
- [Check column 600x400 with 8-28 mm bars](https://www.bctengineer.com/question.md?key=semester_7%2Fdesign_of_rcc_structure%3Acheck-column-600x400-with-8-28) — Design of RCC Structure, chapter 10
- [Footing with load transfer check, 1000 kN](https://www.bctengineer.com/question.md?key=semester_7%2Fdesign_of_rcc_structure%3Afooting-with-load-transfer-check-1000) — Design of RCC Structure, chapter 11