GATE CS 2024 Set 2 Q.41: Regular Expressions, Finite Automata and Regular Languages

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

A 5-state NFA M with states 1 to 5: state 1 is the start state with epsilon transitions to state 2 (accepting) and state 4; states 2 and 3 have mutual transitions on 0; state 3 has an epsilon transition to state 5 (accepting); states 4 and 5 have mutual transitions on 1.

Which one of the following regular expressions represents the language accepted by $M$ ?

$(00)^* + 1(11)^*$

$0^* + (1 + 0(00)^*)(11)^*$

$(00)^* + (1 + (00)^*)(11)^*$

$0^+ + 1(11)^* + 0(11)^*$

Official answer and solution

Official answer: B
From: Official GATE 2024 answer key

Solution

Analyze the accepting paths from start state 1 to accepting state 2 and accepting state 5.

The NFA $M$ has two accepting states, $2$ and $5$ :

Strings accepted at state 2: From state $1$ , take $\epsilon$ to state $2$ , and cycle between states $2$ and $3$ on pairs of 0s. This accepts $(00)^*$ .
Strings accepted at state 5 via state 3: From state $1$ , take $\epsilon$ to state $2$ , read an odd number of 0s ( $0(00)^*$ ) to reach state $3$ , take $\epsilon$ to state $5$ , and cycle between states $5$ and $4$ on pairs of 1s ( $(11)^*$ ). This accepts $0(00)^*(11)^*$ .
Strings accepted at state 5 via state 4: From state $1$ , take $\epsilon$ to state $4$ , read 1 to reach state $5$ , and cycle between $5$ and $4$ on $(11)^*$ . This accepts $1(11)^*$ .

Taking the union of all three sets of accepted strings:

L(M) = (00)^* + 0(00)^*(11)^* + 1(11)^* = (00)^* + (1 + 0(00)^*)(11)^*

Notice that $0(00)^*(11)^*$ already contains $0(00)^*$ (when $(11)^* = \epsilon$ ), and $(00)^* + 0(00)^* = 0^*$ . Hence:

L(M) = 0^* + (1 + 0(00)^*)(11)^*

Final answer

Option (B)

Common trap

Thinking $(00)^*$ cannot be replaced by $0^*$ without noticing that odd-length strings of 0s ( $0(00)^*$ ) are accepted at state 5 via the $\epsilon$ -transition $3 \rightarrow 5$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 41 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source