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 :
Which of the following languages is accepted by the NPDA?
Answer and explanation
Correct answer B
The transition allows the NPDA to accept the empty string immediately (corresponding to ). When reading the first , pushes two 's onto the stack above , and for each subsequent , replaces one with three 's, resulting in a net increase of two 's on the stack per input symbol . Thus, after reading occurrences of , the stack contains symbols of above . Each input symbol pops exactly one via , so exactly occurrences of are required to expose and reach the accepting state via . Hence, the accepted language is .
Practice for these exams
-
UGC NET Computer Science and Applications