regexfinite-automataregular-languageautomata

Understanding (and forming) the regular expression of this finite automaton


enter image description here

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.


Solution

  • 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*(rsr)* = r*(sr*)*.

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

    Step 4 is right since rr = rr and rs + rqs = rs + rqqs.

    Step 5 is right since rs + r = r.

    Step 6 is right since rs = rrs + s.

    Step 7 is right since rs + rqqs = rs + rqs.

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

    Step 9 is right since rr = rr.

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