Site navigation

Consider the following \( \text{NPDA} = (\{q_0, q_1, q_f\}, \{a, b\}, \{1, z\}, \delta, q_0, z,…

The transition \( \delta(q_0, \lambda, z) = \{(q_f, z)\} \) allows the NPDA to accept the empty string \( \lambda \) immediately (corresponding to \( n = 0 \)). When reading…

Choose your answer

Consider the following NPDA=({q0,q1,qf},{a,b},{1,z},δ,q0,z,{qf}) \text{NPDA} = (\{q_0, q_1, q_f\}, \{a, b\}, \{1, z\}, \delta, q_0, z, \{q_f\}) :

δ(q0,λ,z)={(qf,z)} \delta(q_0, \lambda, z) = \{(q_f, z)\}
δ(q0,a,z)={(q1,11z)} \delta(q_0, a, z) = \{(q_1, 11z)\}
δ(q1,a,1)={(q1,111)} \delta(q_1, a, 1) = \{(q_1, 111)\}
δ(q1,b,1)={(q1,λ)} \delta(q_1, b, 1) = \{(q_1, \lambda)\}
δ(q1,λ,z)={(qf,z)} \delta(q_1, \lambda, z) = \{(q_f, z)\}

Which of the following languages L L is accepted by the NPDA?

Select one answer
Answer and explanation

Correct answer B

The transition δ(q0,λ,z)={(qf,z)} \delta(q_0, \lambda, z) = \{(q_f, z)\} allows the NPDA to accept the empty string λ \lambda immediately (corresponding to n=0 n = 0 ). When reading the first a a , δ(q0,a,z)={(q1,11z)} \delta(q_0, a, z) = \{(q_1, 11z)\} pushes two 1 1 's onto the stack above z z , and for each subsequent a a , δ(q1,a,1)={(q1,111)} \delta(q_1, a, 1) = \{(q_1, 111)\} replaces one 1 1 with three 1 1 's, resulting in a net increase of two 1 1 's on the stack per input symbol a a . Thus, after reading n n occurrences of a a , the stack contains 2n 2n symbols of 1 1 above z z . Each input symbol b b pops exactly one 1 1 via δ(q1,b,1)={(q1,λ)} \delta(q_1, b, 1) = \{(q_1, \lambda)\} , so exactly 2n 2n occurrences of b b are required to expose z z and reach the accepting state qf q_f via δ(q1,λ,z)={(qf,z)} \delta(q_1, \lambda, z) = \{(q_f, z)\} . Hence, the accepted language is L={anb2n:n≥0} L = \{a^n b^{2n} : n \ge 0\} .

Practice for these exams

  • UGC NET Computer Science and Applications

Related question papers

Related exam syllabi

Related questions in this topic