Skip to main content

PDA for aⁿb^(3n)

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.

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.]

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

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →