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

Because $n$ is bounded ($n \le 50$), $L$ is a finite language, hence regular, and a minimal DFA exists. Build it directly over $\Sigma=\{a,b\}$ and count the live states plus one trap (dead) state.

Reading the $a$'s. From the start state, scanning $a^{i}$ for $0 \le i \le 50$ lands in a distinct state $A_i$:

$A_0 \xrightarrow{a} A_1 \xrightarrow{a} \cdots \xrightarrow{a} A_{50}.$

These are $51$ states. $A_0$ is the start state and is accepting (since $n=0$ gives $a^{0}b^{0}=\varepsilon \in L$). They are pairwise distinguishable: from $A_i$ the string $b^{i}$ is accepted but $b^{j}$ ($j\ne i$) is not.

Reading one more $a$ from $A_{50}$ would give $a^{51}$, which can never complete to a word of $L$ ($a^{51}b^{51}\notin L$), so $A_{50}\xrightarrow{a}$ trap.

Reading the $b$'s. From $A_i$ with $i\ge 1$, reading a $b$ leaves $i-1$ more $b$'s still required. Track the remaining count $m$ with states $B_m$:

$A_i \xrightarrow{b} B_{i-1},\qquad B_m \xrightarrow{b} B_{m-1}.$

The largest remaining value occurs from $A_{50}$, giving $B_{49}$, so we need $B_0, B_1, \ldots, B_{49}$ — that is $50$ states. $B_0$ is accepting (it marks $a^i b^i$). Each $B_m$ needs exactly $b^{m}$ to accept, so the $50$ states are pairwise distinguishable and distinct from every $A_i$. Any $a$ read while in a $B$ state, or a $b$ read from $B_0$, goes to the trap.

Trap state. One non-accepting dead state absorbs all illegal continuations ($ba$, $a^{51}$, $a^i b^j$ with $j>i$, an $a$ after a $b$, etc.). It is required for completeness of the DFA and is distinct from all the above.

Total:

$\underbrace{51}_{A_0\ldots A_{50}} \;+\; \underbrace{50}_{B_0\ldots B_{49}} \;+\; \underbrace{1}_{\text{trap}} \;=\; 102.$

So the minimal DFA has $102$ states — option 4.

Pitfall: Don't stop at the $51$ $a$-counting states (option 2) or forget the mandatory trap state. A complete DFA needs the dead state, and the descending $b$-counter contributes a separate chain of $50$ states.