StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p><a href="http://krchowdhary.com/toc/dfa-to-reg-exp.pdf" rel="nofollow">http://krchowdhary.com/toc/dfa-to-reg-exp.pdf</a></p> <p>EDIT: Your RE is equivalent to the one provided. here's the reduction of theirs to yours:</p> <pre><code>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*)* </code></pre> <p>Step 1 is right since r(s+t) = rs + rt.</p> <p>Step 2 is right since r*(r*sr*)* = r*(sr*)*.</p> <p>Step 3 is right since r = r + s if L(s) is a subset of L(r).</p> <p>Step 4 is right since r*r = rr* and rs + rq*s = rs + rqq*s.</p> <p>Step 5 is right since rs + r = r.</p> <p>Step 6 is right since r*s = rr*s + s.</p> <p>Step 7 is right since rs + rqq*s = rs + rq*s.</p> <p>Step 8 is right since r = r + s if L(s) is a subset of L(r).</p> <p>Step 9 is right since r*r = rr*.</p> <p>Please feel free to ask any questions or point out any mistakes I may have made.</p> <p>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!!!</p> <p><a href="http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2">http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload