Skip to main content

PDA for aⁱbʲcᵏ with i = j + k

Short answer

Push A for each a. Then pop an A for each b or c, using states to enforce order a* b* c*. Accept if stack returns to Z0 at input end. For aaaabbcc, 4 a's equal 2+2, accepted.

Design a PDA that accepts those strings having the total number of 'a' equal to the sum of the number of 'b' and 'c' in the sequence a, b, c (i.e. aⁱbʲcᵏ : i = j + k). Hence test for "aaaabbcc".

L = { aⁱbʲcᵏ : i = j + k, i, j, k ≥ 0 }. The a's must be matched by the b's and the c's together.

Idea: push A for each a. Each b or c pops one A. The string is accepted if the stack returns to Z0 exactly when the input ends. The order abc* is enforced by the states.

M = ({q0, q1, q2, qf}, {a, b, c}, {A, 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 A
4δ(q1, b, A) = {(q1, ε)}each b pops A
5δ(q0, c, A) = {(q2, ε)}no b's: first c pops A
6δ(q1, c, A) = {(q2, ε)}first c pops A
7δ(q2, c, A) = {(q2, ε)}each c pops A
8δ(q0, ε, Z0) = δ(q1, ε, Z0) = δ(q2, ε, Z0) = {(qf, Z0)}accept
   a,A/AA          b,A/ε            c,A/ε
     ↺               ↺                ↺
 ─► (q0) ─b,A/ε─► (q1) ─c,A/ε─► (q2)
     └──────── c,A/ε ──────────────▲
 each of q0, q1, q2 --ε,Z0/Z0--> ((qf))

(State q0 also reaches qf by ε,Z0/Z0, which accepts the empty string.)

Test for aaaabbcc (i = 4, j = 2, k = 2)

(q0, aaaabbcc, Z0)
⊢ ... 4 moves ...  (q0, bbcc, AAAAZ0)
⊢ (q1, bcc, AAAZ0)   b
⊢ (q1, cc,  AAZ0)    b
⊢ (q2, c,   AZ0)     c
⊢ (q2, ε,   Z0)      c
⊢ (qf, ε,   Z0)      accept

aaaabbcc is accepted because 4 = 2 + 2. A string like aaabbcc (3 ≠ 4) exposes Z0 too early with input left, so it is rejected.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →