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

The automaton has a $0$-region ($q_1\leftrightarrow q_0$ on input $0$) and a $1$-region ($q_2\leftrightarrow$ fourth state on input $1$), joined by a connector. Every accepting run reads a block of $0$s and then a block of $1$s and never returns a $0$ after a $1$, so the language is exactly

$L = 0^{*}1^{*}$

(all strings in which every $0$ precedes every $1$; equivalently, no factor $10$). The trick is to see which option equals $0^{*}1^{*}$.

Each option has the common shape $(00)^{*}\,(\text{bridge})\,(11)^{*}$, where $(00)^{*}$ fixes the parity of the $0$-count and $(11)^{*}$ fixes the parity of the $1$-count. The bridge supplies the missing single $0$ and/or single $1$ to reach the other parity class:

To describe $0^{*}1^{*}$ we need all four parity classes, because $0^{*}1^{*}$ contains strings with any $0$-count and any $1$-count. Only the bridge $\varepsilon+0+1+01$ supplies all four, so only option 4 works. Indeed

$(00)^{*}(\varepsilon+0+1+01)(11)^{*}=0^{*}1^{*},$

since $(00)^{*}(\varepsilon+0)=0^{*}$ and $(11)^{*}(\varepsilon+1)=1^{*}$, giving $0^{*}\,1^{*}$ after distributing the $1$ across the second factor.

The other options each drop a parity class:

• Option 1, $(00)^{*}(0+1)(11)^{*}$: the bridge is mandatory (no $\varepsilon$), so $\varepsilon$, $00$, $11$ are missing.
• Option 2, $(00)^{*}(\varepsilon+0+1)(11)^{*}$: misses the odd-$0$/odd-$1$ class, e.g. $01\notin L$.
• Option 3, $(00)^{*}(\varepsilon+01)(11)^{*}$: keeps only even/even and odd/odd, so $0$ and $1$ are rejected.

Hence the answer is option 4.

Exam trick: When every choice is $(00)^{*}\,(\text{bridge})\,(11)^{*}$, ignore the automaton's exact wiring and classify each candidate by the four $(\text{\#}0,\text{\#}1)$ parity classes its bridge can reach. The full language $0^{*}1^{*}$ needs all four, which singles out $\varepsilon+0+1+01$.