# Regular Expression Simplification

Hi my question about Theory of Computation is:

Let $M$ be defined as follows $$M = (K; E; s; D; F )$$ for \begin{align*} K &= \{q_0, q_1, q_2, q_3\}, \\ E &= \{a, b, c\}, \\ s &= q_0, \\ D &= \{(q_0, abc, q_0), (q_0, a, q_1), (q_0, \epsilon, q_3), (q_1, bc, q_1), (q_1, b, q_2), (q_2, a, q_2), (q_2, b, q_3), (q_3, a, q_3)\}, \\ F &= \{q_0, q_2, q_3\}. \end{align*} Find the regular expression describing $L(M)$. Simplify it as much as you can. Explain your steps.

This is what I found for the regular expression: $$\epsilon + (abc)* + (abc)* a (bc)* ba* + (abc)*a(bc)*ba*b + (abc)*a(bc)*ba*ba* + a*.$$

How does that simplify into this: $$(abc)* a(bc)* + \epsilon + a*ba*?$$

-

## migrated from stackoverflow.comMar 22 '11 at 18:05

This question came from our site for professional and enthusiast programmers.

What have you tried so far, and where did you get stuck? (added the homework tag to your question). –  Robert Harvey Mar 22 '11 at 18:05
Your regexp doesn't simplify to the other. Yours accepts 'abb' but the second one does not. Are you supposed to just translate by inspection or are expected to use the NFA->DFA->regexp algorithm? –  Mitch Mar 23 '11 at 0:58
Your NFA accepts 'abb', so the solution is wrong. Probably you copied the NFA wrongly. –  Yuval Filmus Mar 24 '11 at 5:35
This question might have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! –  Raphael Dec 3 '11 at 17:24