Skip to main content

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

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.

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

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})

#TransitionMeaning
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
  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)

(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).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →