Skip to content
GATEiit

GATE CSE 2024 Session 2 Q22: Regular expression for a two-state DFA

Question

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

Two-state DFA: start state (non-accepting) with a self-loop on 0 and a transition on 1 to the accepting state; the accepting state has a self-loop on 0 and a transition on 1 back to the start state
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: The DFA accepts exactly the strings with an odd number of 1s.

First step: Reach the accepting state with 0∗10^*1; from there a loop is either a 0, or a 1 to the start state, some 0s, and a 1 back.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2024 Session 2 questions →