Consider the following \(\text{NPDA}=\left(\left\{q_{0}, q_{1},…
2022
Consider the following \(\text{NPDA}=\left(\left\{q_{0}, q_{1}, q_{f}\right\}\{a, b\},\{1, z\}, \delta, q_{0}, z,\left\{q_{f}\right\}\right)\)
\(\begin{array}{l} \delta\left(q_{0}, \lambda, z\right)=\left\{\left(q_{f}, z\right)\right\} \\ \delta\left(q_{0}, a, z\right)=\left\{\left(q_{1}, 11 z\right)\right\} \\ \delta\left(q_{1}, a, 1\right)=\left\{\left(q_{1}, 111\right)\right\} \\ \delta\left(q_{1}, b, 1\right)=\left\{\left(q_{1}, \lambda\right)\right\} \\ \delta\left(q_{1}, \lambda, z\right)=\left\{\left(q_{f}, z\right)\right\} \end{array}\)
Which of the following Language \(𝐿\) is accepted by NPDA?
- A.
\(L=\left\{a^{2 n} b^{n}: n \geq 0\right\}\) - B.
\(L=\left\{a^{n} b^{2 n}: n \geq 0\right\}\) - C.
\(L=\left\{a^{2 n} b^{n}: n>0\right\}\) - D.
\(L=\left\{a^{n} b^{2 n}: n>0\right\}\)
Attempted by 88 students.
Show answer & explanation
Correct answer: B
Answer: The NPDA accepts L = {a^n b^{2n} : n ≥ 0}.
Reasoning:
Empty string: the transition δ(q0, λ, z) = (qf, z) immediately accepts the empty string, so n = 0 is included.
First a: when in q0 with z on the stack, δ(q0, a, z) = (q1, 11 z) pushes two '1' symbols and moves to q1. After the first a the stack has 2 ones above z.
Each additional a: in q1 the transition δ(q1, a, 1) = (q1, 111) consumes one top '1' and pushes three '1's, a net increase of two '1's per additional a. So after n a's the stack contains 2n copies of '1' above z.
Each b: in q1 the transition δ(q1, b, 1) = (q1, λ) pops exactly one '1' per b. To return the stack to z the machine must read exactly 2n b's.
Finally, when the stack is back to z, δ(q1, λ, z) = (qf, z) moves to the final state and accepts.
Conclusion: the NPDA accepts exactly the strings with n a's followed by 2n b's, including the empty string (n = 0).