The GATE Grind

GATE 2024 CS (CS2) – Question 41

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

Let $M$ be the 5-state NFA with $\epsilon$-transitions shown: start state 1 with ε to 2 and ε to 4; state 2 (accepting) goes 0 to 3; state 3 goes 0 to 2 and ε to 5; state 4 goes 1 to 5; state 5 (accepting) goes 1 to 4. Which one of the following regular expressions represents the language accepted by $M$?

  1. $(00)^*+1(11)^*$
  2. $0^*+(1+0(00)^*)(11)^*$
  3. $(00)^*+(1+(00)^*)(11)^*$
  4. $0^++1(11)^*+0(11)^*$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $0^*+(1+0(00)^*)(11)^*$

Explanation

From branch via 2/3: (00)* reaches 2 (accept), and 0(00)* reaches 3 then ε to 5, then (11)* loops to accept. From branch via 4: 1(11)* reaches 5. Combined and simplified, the language is 0* + (1+0(00)*)(11)* as in option B.