#TOC what will be the R.E of this DFA?

Question

I'm getting R.E as 0*1(01)*1(0+1)* but people are getting (0+10)*11(1+0)*

Please tell, how!?

Comments

Other peoples are creating loop on the q0 that's why they are getting what you mentioned.

but if you loop on q1 then both initial and final state will seperate and from initial state you can't reached to final state.

---

@Shubhanshu but when i follow state elimination method, I get my R.E as I mentioned. So, what approach should I use which make sure to get correct R.E all the time?!

Answer 1

Multiple people might get multiple RE, you need to check if the language generated by this DFA is accepted by the RE or not.

Example: In above DFA, the language is "string containing 11 as substring".  Let's check RE

Your RE: 0*1(01)*1(0+1)*   It's not accepting 010011, But 010011 is in language, so this is wrong
Other People RE : (0+10)*11(1+0)*  it's accepting 010011, so this is correct

In Similar way, you need to check RE for different strings, and check if these strings are present in Language or not, if you can find any such string that is generated by language and RE is not capable of generating it, that means that RE is wrong.

Also for the same language, multiple RE is possible.

Comments

This happens when you loop on Q1 - 0*1(01)*1(0+1)*

---

@Bikram Sir, please pitch in. How to be sure that we got the correct R.E?

---

You just missed one 0*. Have a look at the below image, hope your all doubts will be cleared.

https://gateoverflow.in/?qa=blob&qa_blobid=6788009942927893806

Answer 2

@iarnav  @ stblue iam getting this is it correct 

Comments

Yes.

Answer 3

yes i too got the same ans

0*1(01)*1(0+1)*

Answer 4

Best way to get the R.E. is

First, start with the first state if you take any path from this and come back to the same state then to do this.

(0 + x)*, as in the above question, x is the path you take for coming back to the state i.e, 10 in this case

Now repeat till you reached the final state.

so (0 + x)*11( 0 + 1)*    -> (0 + 10)*11(0 +1)*