GATE 2022 CS Q.12: solution and answer

GATE 2022 · CSQ.12 · 1 mark · MCQ

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

GATE 2022 CS question 12: A DFA with three states. — Figure from the GATE 2022 CS paper. It is part of the question.

(A)
$a b^{*} ba b^{*} + b a^{*} ab a^{*}$
(B)
$(a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*}$
(C)
$(a b^{*} b + b a^{*} a)^{*} (a^{*} + b^{*})$
(D)
$(b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$

Answer and solution

ANSWER

The language of the automaton is $(b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$ , which is option (D).

Official answer: DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

Read the automaton from the figure. $q_{0}$ is the start state and is not accepting; $q_{1}$ and $q_{2}$ are accepting. Transitions: $q_{0} a q_{1}$ , $q_{1} b q_{1}$ (loop), $q_{1} b q_{0}$ (return edge), $q_{0} b q_{2}$ , $q_{2} a q_{2}$ (loop), $q_{2} a q_{0}$ (return edge). Since $q_{1}$ has two $b$ -edges and $q_{2}$ has two $a$ -edges, the machine is non-deterministic.
Since $q_{0}$ is not accepting, $ε$ is rejected. Every accepted string ends in $q_{1}$ or $q_{2}$ . Split an accepted string at the last time the walk is in $q_{0}$ . Before that point the walk starts and ends at $q_{0}$ . After it, the walk never returns to $q_{0}$ and ends in $q_{1}$ or $q_{2}$ .
Closed walks from $q_{0}$ back to $q_{0}$ are of two kinds. Through $q_{1}$ : read $a$ , then any number of loop symbols $b$ , then the return $b$ , giving $a b^{*} b$ . Through $q_{2}$ : read $b$ , then any number of loop symbols $a$ , then the return $a$ , giving $b a^{*} a$ . Any closed walk is a sequence of these, so the prefix is $(a b^{*} b + b a^{*} a)^{*}$ . This is the same as $(b a^{*} a + a b^{*} b)^{*}$ , because the order inside a union does not matter.
The final part never returns to $q_{0}$ . It is either $q_{0} a q_{1}$ followed by loops, giving $a b^{*}$ , or $q_{0} b q_{2}$ followed by loops, giving $b a^{*}$ . So the final part is $a b^{*} + b a^{*}$ .
Therefore $L = (b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$ , which is option (D).
Check the other options on short strings. (A) needs at least $aba$ , so it rejects $a$ , which the automaton accepts ( $q_{0} a q_{1}$ ). (C) accepts $ε$ , because every factor can be empty, but $q_{0}$ is not accepting. (B) is a union of two expressions, and each one uses only one kind of closed walk. It rejects $abbaab = (ab) (ba) (ab)$ , which the automaton accepts: $q_{0} a q_{1} b q_{0} b q_{2} a q_{0} a q_{1} b q_{1}$ . (D) accepts $abbaab$ through its prefix and final part. So only (D) is correct.

KEY IDEA

Split an accepted string at the last visit to the start state $q_{0}$ . The part before it is a sequence of closed loops through $q_{1}$ ( $a b^{*} b$ ) or $q_{2}$ ( $b a^{*} a$ ). The part after it is a one-way trip to an accepting state ( $a b^{*}$ or $b a^{*}$ ).

WATCH OUT FOR

Treating the machine as deterministic and missing that $q_{1}$ and $q_{2}$ each have a loop and a return edge on the same symbol. Another mistake is choosing (B) or (C): (B) cannot mix visits to $q_{1}$ and $q_{2}$ before ending, and (C) accepts $ε$ even though $q_{0}$ is not accepting.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2022 CS Q.12: solution and answer

Answer and solution

More Finite automata questions