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$?
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.
More Regular Expressions and Finite Automata questions
GATE 2024 CS (CS2) Q62– Let L 1 be the language represented by the regular expression b*ab*(ab*ab*)* and L…
GATE 2023 CS Q14– Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the…
GATE 2023 CS Q63– Consider the language L over the alphabet 0, 1, given below: L = \w \0,1\* w does not…
GATE 2022 CS Q12– Which one of the following regular expressions correctly represents the language of the…
GATE 2021 CS (CS1) Q48– Consider the following language. L = \w \0,1\* w ends with the substring 011\ Which one of…
GATE 2020 CS Q61– Consider the following language. L=\x\a,b\* number of a's in x is divisible by 2 but not…