Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to make an NFA from the following regular expression.

enter image description here

I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.

share|cite|improve this question
Is the empty word ($\lambda$) allowed as input?? – Berci Oct 6 '13 at 0:49
yes. $q6$ could maybe be the final state and $a$ might be another edge $q5 \to q6$ and cut out $q7$ completely. I'm wondering if that would be better – stackuser Oct 6 '13 at 2:09
up vote 1 down vote accepted

You should merge $q_2$ and $q_4$ and remove the $\lambda$-transitions between them, but keep the transition labelled by $c$. You should also replace $q_6 \xrightarrow{a} q_7$ by $q_5 \xrightarrow{a} q_7$. The states $q_6$ and $q_7$ should then be both final.

share|cite|improve this answer
I'm not sure why to merge $q2$ and $q4$. Is it just wrong or is it just extraneous? – stackuser Oct 6 '13 at 17:08
It is not wrong, but it is really unnecessary. Indeed, you have two transitions $q_2 \xrightarrow{\lambda} q_4$ and $q_4 \xrightarrow{\lambda} q_4$ so you can freely pass from $q_2$ to $q_4$ and back. – J.-E. Pin Oct 6 '13 at 21:09

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.