Understanding (and forming) the regular expression

问题:

For the above automaton, the regular expression that has been given in my textbook is the following :

a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

I am having trouble deriving this...the following is my attempt at it :

aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Either I am wrong or I am not being able to simplify it into the form given in the book. Can someone please guide me here, point out the mistake or explain it to me step-by-step?

I'd really really thankful and appreciate that.

回答1:

Check this out. It presents three good, algorithmic methods for answering questions like these. Learn one of them, or all three of them if you have the time or inclination. State removal is fairly intuitive, although I like Kleene's transitive closure method.

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

EDIT: Your RE is equivalent to the one provided. here's the reduction of theirs to yours:

0. a*(a*ba*ba*ba*)*(a+a*ba*ba*ba*)

1. = a*(a*ba*ba*ba*)*a + a*(a*ba*ba*ba*)*a*ba*ba*ba*

2. = a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

3. = a*a + a*(ba*ba*ba*)*a + a*(ba*ba*ba*)*ba*ba*ba*

4. = aa* + a*(ba*ba*ba*)*ba*ba*ba*a + a*(ba*ba*ba*)*ba*ba*ba*

5. = aa* + a*(ba*ba*ba*)*ba*ba*ba*

6. = aa* + aa*(ba*ba*ba*)*ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

7. = aa* + aa*(ba*ba*ba*)* + (ba*ba*ba*)*ba*ba*ba*

8. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + (ba*ba*ba*)*ba*ba*ba*

9. = aa* + aa*(ba*ba*ba*)* + ba*ba*ba* + ba*ba*ba*(ba*ba*ba*)*

Step 1 is right since r(s+t) = rs + rt.

Step 2 is right since r*(r*sr*)* = r*(sr*)*.

Step 3 is right since r = r + s if L(s) is a subset of L(r).

Step 4 is right since r*r = rr* and rs + rq*s = rs + rqq*s.

Step 5 is right since rs + r = r.

Step 6 is right since r*s = rr*s + s.

Step 7 is right since rs + rqq*s = rs + rq*s.

Step 8 is right since r = r + s if L(s) is a subset of L(r).

Step 9 is right since r*r = rr*.

Please feel free to ask any questions or point out any mistakes I may have made.

EDIT2: If you are interested in these kinds of questions, show some love for the new Computer Science StackExchange by going to this link and committing!!!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

回答2:

The textbook seems correct. Taking it step by step:

a*(a*

If this part of the regular expression is true (in other words you do actually read in an 'a'), you will move to state 3. Following the rest of the expression:

ba*

will have you in state 2,

ba*

in state 4 and

ba*

will have you back in state 3.

Now, suppose that you did not read in an 'a' during a*(a*, reading the next b will move you to state 2. You then end up in exactly the same situation as previously, and by following the rest a*ba*ba*) you end up back in state 3.

Since you are now back in state 3, the part (a*ba*ba*ba*)* can execute as many times as it wants, as this will simply be the same as our first scenario (where you read in an 'a' during a*(a*).

The second part simply explains the first scenario again, where you have to read at least one 'a', and then the rest is the same.

Hope this helps, let me know if it still does not make sense. Don't know if my explanation is too clear.