Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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*?$$

share|improve this question

migrated from stackoverflow.com Mar 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.