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

Work over the alphabet $\{0,1\}$ and find the language each expression denotes.

Option 1 — $(0+\varepsilon)(1+10)^{*}$. An optional leading $0$, then a concatenation of the blocks $1$ and $10$. Each block starts with $1$, and inside $10$ the $0$ is immediately followed by the next block (which starts with $1$) or by the end. The optional leading $0$ is followed by a block that starts with $1$ (or by $\varepsilon$). Hence no two consecutive $0$s ever appear, and every such string is generated. So $L_1=\{w \mid w$ has no substring $00\}$.

Option 3 — $(1+01)^{*}(0+\varepsilon)$. The mirror construction: blocks $1$ and $01$ (every $0$ is followed by a $1$), plus an optional trailing $0$. Again exactly the strings with no $00$, so $L_3=L_1$.

Option 4 — $(0+\varepsilon)(11^{*}0)^{*}1^{*}$. The block $11^{*}0$ is "one-or-more $1$s, then a single $0$", so every $0$ is preceded by a $1$; the leading $0$ is optional and is followed by a block starting with $1$; the trailing $1^{*}$ adds only $1$s. No $00$ can appear, and all no-$00$ strings are produced, so $L_4=L_1$.

Option 2 — $(0+\varepsilon)(11+10)^{*}$. Now both body blocks, $11$ and $10$, have length $2$ and start with $1$. Therefore the body $(11+10)^{*}$ produces only even-length strings, with the empty string as the sole short case; its shortest non-empty word has length $2$. With at most one optional leading $0$, this expression cannot generate the single-symbol string $1$:

$1 \in L_1,\,L_3,\,L_4 \quad\text{(take the block } 1\text{)},\qquad 1 \notin L_2 .$

Indeed $L_2$ also misses strings such as $01$ and $111$. Three of the four expressions denote the "no two consecutive $0$s" language, while option 2 denotes a strictly different (smaller) language.

Exam trick: When asked which regex is the odd one out, hunt for a tiny witness string. The blocks $11,10$ are all length-$2$ and force even-length bodies, so the length-$1$ word $1$ instantly separates option 2 from the others.