Skip to main content

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

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.

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

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

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →