Consider the NPDA ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)}, δ(q0, a, z) = {(q1, 11z)}, δ(q1, a, 1) = {(q1, 111)}, δ(q1, b, 1) = {(q1, λ)}, δ(q1, λ, z) = {(qf, z)}. Which language does it accept?

1. A{a²ⁿbⁿ : n ≥ 0}
2. B{aⁿb²ⁿ : n ≥ 0}
3. C{a²ⁿbⁿ : n > 0}
4. D{aⁿb²ⁿ : n > 0}

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. {aⁿb²ⁿ : n ≥ 0}

Explanation

Each a adds two 1's to the stack and each b removes one, so 2n b's are needed for n a's. The empty string is accepted directly from q0, so n ≥ 0.

Note on the official key: the official key says option A. Official/PW key is A ({a²ⁿbⁿ : n ≥ 0}). Each a pushes two 1's and each b pops one, so the machine needs twice as many b's as a's: {aⁿb²ⁿ}.