Find Regular Expression of this DFA

Question

Whenever there are 2 final states, I don't get how to solve it, kindly explain once and for all in a detailed manner! I'll owe you a lot.

Comments

I'm stuck at b*a(b+ab*a)*.

---

In this DFA, State D is unreachable state from the initial state, so remove the D state, now State B & C will be reduced to the same state.

regular expression would be b*a(a+b)*

---

Your answer is right, but please tell the steps you used or what procedure you used.

---

@ soumya singh   is there a way to solve this (b+ab*a)* to get (a+b)* by using some properties or anything?

Answer 1

Remove D state. RE: $b^{*}a(b^{*}a^{*})^{*}$

Comments

@Aghorl - Sorry, your answer is wrong

---

@iarnav

b*a(b*a*)* is equivalent to b*a(a+b)*, therefore @Aghori's answer is correct.

---

@joshi Oh! May you illustrate it how both are equivalent?

---

@iarnav

see this

Answer 2

after minimize dfa  RE = b*a(a+b)*

Comments

@ Poonam Gupta 1 
Can you Convert Given  DFA into RE.

---

Hi yogi,

For the given DFA,

We can easily see that the DFA will accept all string except the ones that contain 101 as a substring.

Now

1) For a 0 we loop over the same state q1 which is final so add 0* to RE

Current RE : 0*

2) On scanning a 1, we reach next final state q2 so add 1 to RE

Current RE : 0*1

3) No matter how many times we scan a 1, we stay at same state so add 1* to RE

Current RE : 0*11*

4) On scanning a zero now, we reach to final state q3 so add 0 to RE

Current RE : 0*11*0

5) Now we cannot scan a 1, else we will reach a dead state. But on scanning a zero we loop over to state q1 which is final so add the loop condition to RE

Final RE : (0*11*0)*

As you can see the above RE will never end in a 101. The minimum string it will end in is epsilon and for characters :  '10'

Please let me know if any errors.

Regards,

Udit

---

It doesn't accept 11001100

Answer 3

For the DFA given in question :

1) We can see that its looping on state 1 for b so we use : b* {Scan all the b's and stay at same state}

2) By scanning a we move to a final state hence we use 'a'

3) Now since weather we scan an 'a' or 'b' we stay at final state hence we use (a+b)* {Universal set}

4) The dead state given in the DFA is not reachable in any way hence we ignore it.

Final RE obtained b*a(a+b)*