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

The diagram is a Moore machine with six states; only $S_5$ outputs $1$, so a string is recognized exactly when it drives the machine into $S_5$. Reading the labels (vertical edges $=1$, horizontal/self edges $=0$) gives the transition table:

The accepting state $S_5$ is reached only from $S_3$ on a $0$, or from $S_4$ on a $1$. Tracing each option:

• Option 1 — $0^{+}1$: $00\ldots01$ runs $S_0\xrightarrow{0}S_2\xrightarrow{0}S_4(\xrightarrow{0}S_4)^{*}\xrightarrow{1}S_5$. Recognized (e.g. $001$).
• Option 2 — $0\,1^{+}0$: $S_0\xrightarrow{0}S_2\xrightarrow{1}S_3(\xrightarrow{1}S_3)^{*}\xrightarrow{0}S_5$. Recognized (e.g. $010$).
• Option 4 — $1^{+}0\,1^{+}0$: $1010$ runs $S_0\xrightarrow{1}S_1\xrightarrow{0}S_3\xrightarrow{1}S_3\xrightarrow{0}S_5$. Recognized.
• Option 3 — $1^{+}0$: any number of $1$s holds the machine at $S_1$ ($S_0\xrightarrow{1}S_1\xrightarrow{1}S_1\cdots$); the following $0$ moves $S_1\xrightarrow{0}S_3$. It stops at $S_3$, whose output is $0$ — never $S_5$.

So $1^{+}0$ can never reach the accepting state and is the one pattern the machine cannot recognize.

Exam trick: "recognize" in a Moore recognizer means "land on a state whose output is $1$." Trace the last state, not just whether a valid path exists — $1^{+}0$ ends in $S_3$ (output $0$), so it is rejected even though the path is legal.