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

Given DFA with $\sum = {0, 1}$ & p, q, r, s are the given states.

State s is the initial state & State p is the final state.

 

                                          

 

From, this DFA A, we can directly conclude few points :

1. State r is the Dead State.
    
2. DFA A, is designed to accept all strings which starts with 1.
    
3. The smallest string that will be accepted is 1.

 

With conclusion 3, Option B is rejected.

 

NOTE : Dead State : A state is called Dead State when there is no way to go to final state from

that state. 

OR

If we reach on such state there is no way to reach the final state.

 

Now, the Regular Expression of DFA A, can be concluded as :

As, it is designed to accept those strings starting with 1. 

On state s, after reading 1 we will go to state p, which is the final state.

So, Regular Expression will starts with 1, which matches with Option A, C & D.

 

On reaching state p, we have 2 independent paths :

1. Keep looping on state p, by reading 0 again and again.
    
2. Reading 11 for coming back to final state p.

 

As mentioned, these 2 paths are independent.

So, we have choice between 0 & 11, there is no fixed order between them.

 

Final RE : $1(0+11)^{*}$. Option C is Correct Answer.

 

Why Option A is Rejected ?

In Option A, after reading 1 they are fixing the order of 2 independent paths 0 & 11.

$1(0^{*}11)^{*}$ , here 11 is fixed after 0, which is wrong.

 

Why Option D is Rejected ?

In Option D, after reading 1 they are again fixing the order of 2 independent paths 0 & 11.

$1(110^{*})^{*}$ , here 0 is fixed after 11, which is wrong.

Answer 2

Detailed Video Explanation:

GATE CSE 2023 - Question 4 - DFA to Regular Expression

We can delete the state $q$ by making a self loop on state $p$ with label $11,$ and by adding an edge from state $p$ to $r$ with label $10.$

So, the set of strings that end in the state $p$ can be given by the regular expression  $1(0+11)^*.$

Answer 3

The given finite automata generate string like $(1,10,111,100,11111,1011,1110,10000,101111,10011...\infty)$ .

Start with $1$ to reach the final state.after that we have $2$ choices as $(0+11)^*$.

$\therefore $ R.E.= $1(0+11)^*$

Option (A): it is wrong because it will not generate strings like $10$

Option (B): it is wrong because it will generate $0$ which is rejected in the given DFA.

Option (D): it is wrong because it will not generate strings like $10,100.$
Option (C) is correct.

Comments

Sir $110$ is going to dead state, this string is not accepting string by the given automata.

---

it is a typo, the string is $100$, updated.

Answer 4

option C is correct. just make a new final state with null move and try to eliminate states between new final state and intial state