What language is accepted by the PDA M = ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) where in q0 every input symbol is pushed, δ(q0, λ, a) = {(q1, a)}, δ(q0, λ, b) = {(q1, b)}, in q1 a matches a and b matches b (pop), and δ(q1, λ, z) = {(q2, z)}?

1. AL = {w | nₐ(w) = n_b(w), w ∈ {a, b}⁺}
2. BL = {w | nₐ(w) ≤ n_b(w), w ∈ {a, b}⁺}
3. CL = {w | n_b(w) ≤ nₐ(w), w ∈ {a, b}⁺}
4. DL = {wwᴿ | w ∈ {a, b}⁺}

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

Show answer & explanation

Correct answer: D. L = {wwᴿ | w ∈ {a, b}⁺}

Explanation

q0 pushes the first half, nondeterministically switches to q1, then pops matching symbols in reverse order, accepting when the stack is back to z. That is the even-length palindromes wwᴿ.