GATE CSE 2023 | Question: 4

Question

Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{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.

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

• A. $1\left(0^{*} 11\right)^{*}$
• B. $0(0+1)^{*}$
• C. $1(0+11)^{*}$
• D. $1\left(110^{*}\right)^{*}$

Comments

C

Answer 1

We can remove the state r as it is dead state, hence we end up with remaining 3 states

The transtions (p,1) and (q,1)can be converted to (11)* as self loop on state p after elimination of state q

So, we end up wth two states s and p, now on p the self loop is (0+11)*

So the regular expression is 1(0+11)*, which is option C