GATE CS 2024 Set 2 — Question 41

The language accepted by the NFA can be analyzed by decomposing it into paths:

• Start at state 1, go to state 2 via $\epsilon$.
• Loop between states 2 and 3: $2 \xrightarrow{0} 3 \xrightarrow{0} 2$. This loop generates $(00)^*$.
• To reach the final state 5, we must transition from 2 to 3 (reading '0') and then from 3 to 5 (reading $\epsilon$).
• So, the path purely through the top component generates strings of the form $0(00)^*$, which represents an odd number of 0s.

2. Bottom Path (States 1, 4, 5):

• Start at state 1, go to state 4 via $\epsilon$.
• Transition $4 \xrightarrow{1} 5$ (reading '1').
• Loop between states 5 and 4: $5 \xrightarrow{1} 4 \xrightarrow{1} 5$. This loop generates $(11)^*$.
• So, the path purely through the bottom component generates strings of the form $1(11)^*$, which represents an odd number of 1s.

3. Combined Path (Top to Bottom):

• The NFA allows transitioning from the top component to the bottom component because state 5 is shared.
• Once the automaton reaches state 5 via the top path (consuming $0(00)^*$), it is in an accepting state.
• However, from state 5, it can also traverse the bottom loop ($5 \to 4 \to 5$) any number of times, generating sequences of $(11)^*$.
• Therefore, strings generated by going through the top path and then optionally looping in the bottom component are of the form $0(00)^* (11)^*$.

Total Language:
The language is the union of the bottom path alone and the top path (extended by the bottom loop):$$L = 1(11)^* \cup 0(00)^* (11)^*$$Analyzing the Options:

• (A) $(00)^* + 1(11)^*$: Represents even 0s or odd 1s. Incorrect.
• (B) $0^* + (1 + 0(00)^*)(11)^*$: This expands to $0^* + 1(11)^* + 0(00)^*(11)^*$. The term $0(00)^*(11)^*$ correctly captures the "Odd 0s followed by Even 1s" pattern derived above. The term $1(11)^*$ captures the "Odd 1s" pattern. Although $0^*$ adds even 0s (which aren't strictly in the derived language), this option is the only one that correctly describes the mixing of 0s and 1s ($0(00)^*(11)^*$).
• (C) $(00)^* + (1 + (00)^*)(11)^*$: The mixing term $(00)^*(11)^*$ represents Even 0s followed by Even 1s. Incorrect.
• (D) $0^+ + 1(11)^* + 0(11)^*$: The mixing term $0(11)^*$ is a subset of $0(00)^*(11)^*$ and misses strings like $00011$. Incorrect.

Thus, Option (B) is the correct representation.