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

We evaluate each of the four claims; exactly one is correct.

Claim (a) — TRUE. Build an $\varepsilon$-free NFA with a single accepting state $F$ for $\{a\}\cup\{b^n : n\ge 2\}$:

$\delta(q_0,a)=\{F\},\quad \delta(q_0,b)=\{q_1\},\quad \delta(q_1,b)=\{q_1,F\}.$

Here $q_0$ is the start state and $F$ has no outgoing transitions. Reading $a$ gives $q_0\to F$ (accepts $a$); reading $b^n$ with $n\ge 2$ gives $q_0\xrightarrow{b}q_1(\xrightarrow{b}q_1)^{*}\xrightarrow{b}F$. Since $F$ is a dead-end, a string like $ab$ cannot reach $F$. Thus a one-final-state, $\varepsilon$-free NFA does exist.

Claim (b) — FALSE. Take $L_2=\Sigma^{*}$ (regular) and $L_1=\{a^n b^n : n\ge 0\}$ (not regular). Because $\varepsilon\in L_1$, both $L_1L_2=\Sigma^{*}$ and $L_2L_1=\Sigma^{*}$ are regular, yet $L_1$ is not. So regularity of $L_2,\,L_1L_2,\,L_2L_1$ does not force $L_1$ regular.

Claim (c) — FALSE. $L(M_1)\cap\overline{L(M_2)}=\varnothing$ says only $L(M_1)\subseteq L(M_2)$ — one inclusion. Equivalence $L(M_1)=L(M_2)$ needs the symmetric difference to be empty, i.e. also $\overline{L(M_1)}\cap L(M_2)=\varnothing$. Counterexample: $L(M_1)=\varnothing\subseteq L(M_2)=\Sigma^{*}$ satisfies the stated condition but $M_1,M_2$ are not equivalent.

Claim (d) — FALSE. For a complete DFA, swapping accepting and non-accepting states yields a DFA for $\overline{L}$ — that part is correct. But the result is still minimal: $L$ and $\overline{L}$ induce the same Myhill–Nerode equivalence classes (two strings are distinguishable for $L$ iff they are for $\overline{L}$), so their minimal DFAs have the same number of states. Swapping keeps every state reachable and every pair distinguishable, so the machine is necessarily minimal.

Only claim (a) holds $\Rightarrow$ 1 correct claim, option 1.

Pitfall: $L(M_1)\cap\overline{L(M_2)}=\varnothing$ tests containment, not equality — DFA equivalence requires both $L(M_1)\setminus L(M_2)$ and $L(M_2)\setminus L(M_1)$ to be empty.