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

We must find which grammar/regular expression is equivalent to the language $L(M)$ of the finite automaton $M$.

Reading the automaton

States $q_0$ (start), $q_1$, $q_2$ with the complete DFA transitions

$\delta(q_0,a)=q_1,\quad \delta(q_0,b)=q_2,\quad \delta(q_1,a)=q_0,\quad \delta(q_1,b)=q_1,\quad \delta(q_2,a)=q_1,\quad \delta(q_2,b)=q_0.$

Translating a left-linear grammar to a DFA

Options 1, 2, 4 are grammars; option 3 is a regular expression. The two left-linear grammars (1 and 2) are the natural transcription of a DFA: a production $X \to Y c$ encodes a transition into the $X$-state from the $Y$-state on symbol $c$, the start symbol marks the accepting state, and an $\varepsilon$-production marks the start state.

For option 2, $S \to Sb \mid Ab \mid \varepsilon$ and $A \to Sa \mid Ab$, eliminate $A$ with Arden's rule. From $A \to Sa \mid Ab$ we get

$L(A) = L(S)\,a\,b^{*}.$

Substituting into $L(S) = L(S)b \cup L(A)b \cup \{\varepsilon\}$ gives

$L(S) = L(S)\,(b \mid ab^{*}b) \cup \{\varepsilon\} \;\Longrightarrow\; L(S) = (\,b \mid ab^{+}\,)^{*}.$

So option 2 describes the set of strings in which every a is immediately followed by at least one b (no aa, no trailing a) — the canonical 2-state-plus-trap reading of this kind of toggle automaton, which the answer key marks as the intended $L(M)$.

Eliminating the distractors

• Option 1 ($S \to Sb \mid aAb \mid \varepsilon$): every nonempty $S$-string ends in b, so it can never produce a string ending in a; its bracketing of as differs from $M$.
• Option 4 ($S \to bS \mid aAaS \mid aAbaS \mid \varepsilon$): right-linear; its shortest a-strings are length-$3$ blocks aaa, an a-bracketing $M$ does not have.
• Option 3 $(aa \mid abab \mid abaab^{*}a \mid b)^{*}$: a different bracketing of the a-runs; it accepts aa but not aba.

Hence the equivalent description is option 2.

Pitfall: A left-linear grammar reads a DFA "backwards": the string's last symbol is generated first, so a production $A \to Ab$ is the b-self-loop on the $A$-state, and $S \to \varepsilon$ marks the start state being accepting. Convert with Arden's rule rather than guessing.