Skip to content
GATEiit

GATE CSE 2023 Q14: Regular expression for a four-state DFA

Question

Consider the Deterministic Finite-state Automaton (DFA) A\mathcal{A} shown below. The DFA runs on the alphabet {0,1}\{0, 1\}, and has the set of states {s,p,q,r}\{s, p, q, r\}, with ss being the start state and pp being the only final state.

DFA: start state s goes to p on 1 and to r on 0. Final state p loops on 0 and goes to q on 1. State q goes back to p on 1 and to r on 0. State r loops on 0 and 1 (dead state)
Tap the figure to enlarge

Which one of the following regular expressions correctly describes the language accepted by A\mathcal{A}?

Try it: multiple choice: exactly one correct option

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

Answer: C (official GATE 2023 final answer key)

Concept used: Reading a regular expression off a DFA by following the loops through the final state.

First step: From ss the only way to pp is on 1; then list the ways to leave pp and come back to it (00, or 1111).

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 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2023 questions →