GATE CSE 2024 | Set 2 | Question: 31

Question

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

Which one of the following regular expressions represents the language accepted by $\text{M}$?

• A. $(00)^{*}+1(11)^{*}$
• B. $0^{*}+\left(1+0(00)^{*}\right)(11)^{*}$
• C. $(00)^{*}+\left(1+(00)^{*}\right)(11)^{*}$
• D. $0^{+}+1(11)^{*}+0(11)^{*}$

Answer 1

Video Solution: NFA to Regular Expression - GATE CSE 2024

Counter-example for option A: $011$ is not generated.

Counter-example for option C: $000$ is not generated.

Counter-example for option D: empty string is not generated. 

WHY Option B: See HERE.

Answer 2

From Question minimum Empty string is accepted so Option D is eliminated,

Also A & C option is restricting for 0's to be in multiple of 2 so A & C eliminated as we can have any multiple of 0 even or odd so Answer is option B