---
title: "PDA for aⁱbʲcᵏ with i = j + k"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:pda-i-equals-j-plus-k"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-i-equals-j-plus-k
site: BCT Engineering
---

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

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2073 Chaitra
- Video: [Design PDA for L= { a^i b^j c^k | i,j,k=1 & onwards and i= j+k }](https://www.youtube.com/watch?v=2zGvtHTHB04) — Learn with ART
- 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-i-equals-j-plus-k
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

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

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

## Answer

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 a*b*c* is enforced by the states.

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

| # | Transition | Meaning |
|---|---|---|
| 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 |

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

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does the PDA check i = j + k?
   A. Push A for each a; each b or c pops one A; accept when stack is Z0 at the end
   B. Push for b and c; pop for a
   C. Compare b with c only
   D. Use two stacks
   Answer: A. The a's are matched against b's and c's together. (Key point: Strategy)

2. How is the order a*b*c* enforced?
   A. By the stack alphabet
   B. By states q0, q1, q2 with no moves allowing a after b or b after c
   C. By pushing different symbols
   D. It is not enforced
   Answer: B. Each state only allows the symbols that can validly follow. (Key point: Order enforced)

3. Why is there a move δ(q0, c, A) to q2?
   A. To accept c only
   B. To handle j = 0, when c's follow the a's directly
   C. To push c
   D. To reject strings
   Answer: B. If there are no b's, the first c must pop an A straight from q0. (Key point: Transition 5)

4. Why is aaabbcc rejected?
   A. Z0 is exposed too early, leaving input
   B. The c's come first
   C. The a's are too few
   D. It has no b
   Answer: A. 3 a's but 4 pops: the stack empties with input remaining, so there's no accepting path. (Key point: Rejecting aaabbcc)

## Related in Theory of Computation

- [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 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^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^(2n+1)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b2n-plus-1) — 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

- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×