--- title: "PDA configuration; PDA for a^(3n)b^n" subject: "Theory of Computation" chapter: 3 key: "semester_3/theory_of_computation:pda-config-a3n-bn" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-config-a3n-bn site: BCT Engineering --- # PDA configuration; PDA for a^(3n)b^n Theory of Computation · Chapter 3: Context Free Grammar - Asked in: 2072 Chaitra - Video: [Theory of Computation: PDA Example (a^n b^2n)](https://www.youtube.com/watch?v=K_kYGkeP3L8) — Anita R - 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-config-a3n-bn - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3 ## Question Define the configuration of a PDA. Design the PDA that accepts L = {a^(3n) b^n, n > 0} and check the string aaaaaabb. ## Short answer A configuration is (q, w, γ) where q is state, w is remaining input, γ is stack top. The PDA pushes one A per a, then for each b pops three A's via states q0,q1,q2,q3. The string aaaaaabb (n=2) is accepted as it empties the stack. ## Answer #### Configuration (instantaneous description) of a PDA A PDA is M = (Q, Σ, Γ, δ, q0, Z0, F). Its **configuration** is the triple (q, w, γ) ∈ Q × Σ* × Γ* where q is the current state, w is the **unread** part of the input, and γ is the stack contents (top at the left). One move is written (q, aw, Xγ) ⊢ (p, w, βγ) when (p, β) ∈ δ(q, a, X). The initial configuration is (q0, input, Z0). The input is accepted if some sequence of moves reaches a configuration with the input fully read and a final state. #### PDA for L = { a³ⁿbⁿ : n > 0 } Idea: push A for every a. For each b, pop **three** A's (the first pop on reading b, the other two by ε-moves). M = ({q0, q1, q2, q3, qf}, {a, b}, {A, Z0}, δ, q0, Z0, {qf}) | # | Transition | Meaning | |---|---|---| | 1 | δ(q0, a, Z0) = {(q0, AZ0)} | push first A | | 2 | δ(q0, a, A) = {(q0, AA)} | push A for each a | | 3 | δ(q0, b, A) = {(q1, ε)} | first b: pop one A | | 4 | δ(q1, ε, A) = {(q2, ε)} | pop second A | | 5 | δ(q2, ε, A) = {(q3, ε)} | pop third A | | 6 | δ(q3, b, A) = {(q1, ε)} | next b: pop one A | | 7 | δ(q3, ε, Z0) = {(qf, Z0)} | all matched: accept | ```text a,Z0/AZ0 b,A/ε ε,A/ε ε,A/ε a,A/AA ↺ ε,Z0/Z0 ─► (q0) ───────► (q1) ────► (q2) ────► (q3) ───────► ((qf)) ▲ │ └──────── b,A/ε ─────┘ ``` #### Check for aaaaaabb (6 a's, 2 b's, so n = 2) ```text (q0, aaaaaabb, Z0) ⊢ ... six moves reading a ... (q0, bb, AAAAAAZ0) ⊢ (q1, b, AAAAAZ0) b: pop ⊢ (q2, b, AAAAZ0) ε: pop ⊢ (q3, b, AAAZ0) ε: pop ⊢ (q1, ε, AAZ0) b: pop ⊢ (q2, ε, AZ0) ε: pop ⊢ (q3, ε, Z0) ε: pop ⊢ (qf, ε, Z0) accept ``` The input is consumed and the machine is in the final state qf, so **aaaaaabb is accepted**. A string such as aaaabb (4 a's) would get stuck at q1 with Z0 on top, so it is rejected. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a configuration of a PDA? A. (q, w, γ): state, unread input, stack contents B. (q, w): state and unread input only C. (q, γ): state and stack only D. The set of final states Answer: A. A PDA configuration is a triple of current state, unread input and stack. (Key point: PDA configuration) 2. How does the PDA for a³ⁿbⁿ match the b's? A. Pushes three A's for each b B. Pushes A for each a and pops three A's for each b C. Pops one A per b D. Counts with states only Answer: B. Each b must cancel three a's, so three A's are popped per b. (Key point: Strategy) 3. How are the second and third A's popped for one b? A. By reading two more b's B. By ε-moves in states q1 and q2 C. By pushing Z0 D. They are not popped Answer: B. After popping one A on reading b, ε-moves q1→q2 and q2→q3 pop two more without input. (Key point: ε-moves for pops) 4. Why is aaaabb rejected? A. It starts with a B. It contains b C. The second b needs 3 A's but only 1 remains, so the PDA gets stuck with Z0 on top D. It has too many a's Answer: C. 4 a's cover only one b with 3 pops; the leftover single A cannot be popped three times. (Key point: Rejecting aaaabb) ## 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 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 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ʲcᵏ with i = j + k](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-i-equals-j-plus-k) — 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 - [String insulator configuration and advantages](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Astring-insulator-configuration) — Transmission and Distribution System Design, chapter 3 - [400 kV lines: configuration, V-string, earth wires](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Ajustify-400kv-config-vstring-earthwire) — Transmission and Distribution System Design, chapter 4 - [Check string consists of alphabet only](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Astring-alphabet-check) — Computer Programming, chapter 7 - [Journal bearing design with film thickness check](https://www.bctengineer.com/question.md?key=semester_6%2Fmachine_design_i%3Ajournal-bearing-minimum-film-thickness) — Machine Design I, chapter 7