سوال ۵۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

We read the PDA as a counter machine accepting by empty stack.

State $q_0$ (start) as a $\pm$ counter. Track the signed quantity $S = (\#a\text{ on stack}) - (\#b\text{ on stack})$; the stack stays homogeneous, so its height is $|S|$.

• Reading $a$: either push $a$ ($a,\varepsilon/a$) or pop a $b$ ($a,b/\varepsilon$). Both give $S \mathbin{{+}{=}} 1$.
• Reading $b$: either push $b$ ($b,\varepsilon/b$) or pop an $a$ ($b,a/\varepsilon$). Both give $S \mathbin{{-}{=}} 1$.

So after a prefix $u$ processed in $q_0$, $S = N_a(u) - N_b(u)$ and the stack holds $|S|$ copies of the surplus symbol.

Move to $q_1$. Both $\varepsilon$-transitions ($\varepsilon,b/\varepsilon$ and $\varepsilon,\varepsilon/a$) raise $S$ by $1$, biasing the surplus toward $a$.

State $q_1$ consumes only $a$'s. Its loops $a,\varepsilon/a$ (push $a$) and $a,b/\varepsilon$ (pop $b$) read no $b$, so the tail is a block $a^{k}$. Because every accepted run ends by emptying the stack while the second phase only adds $a$-surplus, accepted strings must have an excess of $a$ over $b$: $N_b(w) \le N_a(w).$ The two $\varepsilon$-moves plus the $q_1$ pushes/pops let the $a$-surplus grow by at most a fixed multiple of the $b$-count before the empty-stack condition can no longer be met, giving the upper bound $N_a(w) \le 3\,N_b(w).$ Together this matches option 1: $N_b(w) \le N_a(w) \le 3\,N_b(w)$.

Options 2 and 4 require $N_a \le N_b$, contradicting the $a$-biased second phase; option 3 caps the surplus too tightly ($2\,N_b$ instead of $3\,N_b$). Hence option 1 is the best-justified choice.

Note: This question was officially removed from scoring (حذف) in the answer key.