The GATE Grind

GATE 2023 CS – Question 14

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being the start state and p being the only final state. [Figure: s --1--> p, s --0--> r; p --0--> p, p --1--> q; q --1--> p, q --0--> r; r loops on 0,1.] Which one of the following regular expressions correctly describes the language accepted by A?

Diagram for GATE 2023 CS question 14
  1. $1(0^*11)^*$
  2. $0(0+1)^*$
  3. $1(0+11)^*$
  4. $1(110^*)^*$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $1(0+11)^*$

Explanation

The first symbol must be 1 to reach p. From p, 0 loops on p, and 11 goes p→q→p. Any other move reaches the dead state r, giving 1(0+11)*.