1,336 views
2 votes
2 votes

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

Please tell, how!?

4 Answers

Best answer
2 votes
2 votes
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.
selected by
0 votes
0 votes
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)*

Related questions

2 votes
2 votes
1 answer
1
iarnav asked Aug 16, 2017
758 views
I'm getting (a+ba*b)*a*b
0 votes
0 votes
2 answers
2
iarnav asked Mar 14, 2019
863 views
Given L = { 0*1 + 0 + 1* + 10*1}where + symbol is UNION and NOT positive closure.Please draw the Minimal DFA for this.
2 votes
2 votes
2 answers
3
iarnav asked Aug 29, 2017
943 views
input {a,b} Write R.E where every b is followed by at least 2 K a's? (K is +ve integer)
3 votes
3 votes
2 answers
4
iarnav asked Aug 29, 2017
2,237 views
input {0,1} Set of all strings that begin and end with either 0 or 1. What does this statement/line means and what would be the R.E for this?