Skip to main content

PDA configuration; PDA for a^(3n)b^n

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.

Define the configuration of a PDA. Design the PDA that accepts L = {a^(3n) b^n, n > 0} and check the string aaaaaabb.

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

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →