Converting DFA to RE

Question

I am using JFLAP to convert a DFA to RE for the language

"Even a and Odd b"

This last step is not clear to me as shown in figure how it get this final RE

final RE

((ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*(a(bb)*ba+b))*(ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*

My confusion is at the term a(bb)*ba+b (Q1 TO Q0), why it has star in final expression

Answer 1

I have relabeled the transitions of the NFA in your diagram so the explanation is simpler.

Doing so leaves you with the regex:

 (R1* R2 R3* R4)* R1* R2 R3*

The first parenthesized section is essentially describing a sequence of steps that get you from q0 back to q0. The regex says, do this as much as you want and when you're done messing around, you can follow R1 as many times as you want to still stay in state q0 and when you're really done messing around, follow R2 to get to the final state where you can loop on R3 as much as you want.

This not the neatest or most intuitive way to have state eliminated the NFA into a regex but I think it is correct. Hopefully the explanation makes sense. If not, ask in the comments!

As a reference, I've written the regex I came up with. Note I use | instead of + as you have.

(aa|ab(bb)*ba)* (ab(bb)*a|b) ((a(bb)*a)* ((a(bb)*ba|b)(aa|ab(bb)*ba)*(ab(bb)*a|b))*)*

Edit:

You want your regex to capture all possible patterns that will eventually lead you to the final state, starting from state q0. Now imagine you are standing at state q0. What actions could you make? You could split up your set of actions into those that will keep you in state q0 and those that will get you in q1.

Actions that will keep you in q0:

• Follow R1
• Follow R2, do whatever messing around you can in q1, and then come back to q0 by following R4. Let us call this regex R2_R4 where that blank needs to be filled with all possible things we can do in q1 except coming back via R4. Well the only thing in q1 we can do is follow R3 a bunch of times so we replace the blank with R2R3*R4.

By enumerating all the ways you can stay in q0, you're essentially getting rid of the transition from q1 to q0 (R4). In other words, you're saying after this portion of my regex, if you go to state q1, there should be no way of coming back to q0 (if there were it would be captured by the first part of the regex). So your NFA now kind of looks like this:

So you final regex would be, follow the transition that stays in q0, then go to q1 via R2, and stay in q2 as long as you want by following R3. So your regex could look like:

 (R1 + R2R3*R4)* R1* R2 R3*

which actually is equivalent to the one you have:

 (R1* R2 R3* R4)* R1* R2 R3*

because the or nature of (R1+R2 R3* R4)* is equivalent to (R1* R2 R3* R4)*. I actually think the version with the or (+) is clearer but it doesn't really matter as long as it works.