GATE CS 2024 Set 2 | Question 41

Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below.

NFA with states 1 to 5: state 1 is the start state and states 2 and 5 are accepting (double circles). State 1 has epsilon-transitions to states 2 and 4, states 2 and 3 are joined by 0-transitions in both directions, state 3 has an epsilon-transition to state 5, and states 4 and 5 are joined by 1-transitions in both directions.

Which one of the following regular expressions represents the language accepted by \(M\) ?

Option A: \((00)^{*} + 1(11)^{*}\)
Option B: \(0^{*} + (1 + 0(00)^{*})(11)^{*}\) (correct)
Option C: \((00)^{*} + (1 + (00)^{*})(11)^{*}\)
Option D: \(0^{+} + 1(11)^{*} + 0(11)^{*}\)

Answer

(B)

Explanation

Follow the two \(\epsilon\)-moves out of the start state 1.

Into state 2, which accepts: the 0-loop through state 3 accepts \((00)^{*}\). From state 3, reached after an odd number of 0s, the \(\epsilon\)-move enters the accepting state 5, where the 1-loop adds any number of 11s: \(0(00)^{*}(11)^{*}\).
Into state 4: one 1 reaches state 5, and each further 11 returns there: \(1(11)^{*}\).

So \(L(M) = (00)^{*} + 0(00)^{*}(11)^{*} + 1(11)^{*}\). Because \(0^{*} = (00)^{*} + 0(00)^{*}\) and \(0(00)^{*}\) is already inside \(0(00)^{*}(11)^{*}\), this is exactly option (B). Option (A) misses 0, (C) misses 0 and wrongly accepts 11, and (D) misses the empty string and 00011.

Answer: B