Home › Previous year questions › GATE 2024 CS (CS2) › Question 22GATE 2024 CS (CS2) – Question 22 Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? (Two states: start state q0 (non-accepting) with self-loop on 0 and transition on 1 to q1; accepting state q1 with self-loop on 0 and transition on 1 back to q0.)
$0^*1(0+10^*1)^*$ $0^*(10^*11)^*0^*$ $0^*1(010^*1)^*0^*$ $0(1+0^*10^*1)^*0^*$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (A) $0^*1(0+10^*1)^*$
Explanation The DFA accepts strings with an odd number of 1s. From q0: 0*1 reaches q1; then any loop returning to q1 is either 0 or 1 0* 1. So 0*1(0+10*1)*.
More Regular Expressions and Finite Automata questions GATE 2024 CS (CS2) Q41 – Let M be the 5-state NFA with -transitions shown: start state 1 with ε to 2 and ε to 4;… 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… All Regular Expressions and Finite Automata questions →