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

Claim. Every DFA $M=(Q,\Sigma,\delta,q_0,F)$ has an equivalent DFA whose start state has no incoming transitions. So the answer is always yes (option 1).

Construction. Add one fresh state $q_0'\notin Q$ and make it the new start state. Give it exactly the same outgoing behavior as the old start state: $\delta'(q_0',a)=\delta(q_0,a)\quad\text{for every }a\in\Sigma .$ Keep every original transition unchanged, and make the new state accepting exactly when the old start state was, to preserve the empty string: $q_0'\in F'\iff q_0\in F .$ Formally $M'=(Q\cup\{q_0'\},\,\Sigma,\,\delta',\,q_0',\,F')$ with $F'=F\cup\{q_0'\}$ if $q_0\in F$, else $F'=F$.

Why it works.

• $q_0'$ is brand new, and no transition is ever directed into it (the old transitions are untouched and none of them targeted a state that did not exist), so $q_0'$ has no incoming edge.
• For any input $w=a_1a_2\cdots a_n$ with $n\ge 1$, the first move sends $q_0'\to\delta(q_0,a_1)$, after which $M'$ is in an ordinary state of $M$ and follows $M$'s transitions identically. Hence $\hat\delta'(q_0',w)=\hat\delta(q_0,w)$.
• For $w=\varepsilon$, acceptance is decided by the start state itself, and we set $q_0'$ accepting iff $q_0$ was, so $\varepsilon$ is handled correctly too.

Therefore $L(M')=L(M)$, and $M'$ is a DFA whose start state has no incoming edge. The transformation needs no assumption about self-loops or edges from final states, which rules out options 3 and 4; and it works for every language, ruling out option 2.

Exam trick: "Make the start state un-enterable" is a standard normal-form move — just clone the start state into a fresh, never-targeted state and copy its accepting status to keep $\varepsilon$. The old start state may still keep its incoming edges; that is fine because it is no longer the start state.