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 have drawn my answers in paint, are they correct?

(4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions:

(i) 0

My Answer 4ci

(ii) 1 | 0

My Answer 4cii

(iii) 0 * (1 | 0)

My Answer 4cii

share|cite|improve this question
Your 4ciii solution can be much simpler. Hint -- construct an automaton for $0^*$. Then think how to convert that into an automaton for $0^*(1|0)$, realizing there are two cases to that, and you can apparently use $\epsilon$ moves. – David Lewis Apr 26 '12 at 7:23
up vote 1 down vote accepted

i This works, but why do you bother with the arrow labelled 1? It appears that you are not requiring your automata to be complete, and so you can eliminate every state that doesn't lie on a path to a final state.

ii This is fine.

iii As David Lewis commented, this is much more complicated than necessary. Look at each of your $\epsilon$-transitions and consider whether it is really achieving anything. Some of them do have a purpose, but most of them don't. The tidiest automaton for this language doesn't have any $\epsilon$-transitions. Your automaton does recognise the right language, though.

share|cite|improve this answer
When I saw the solution to (iii), it appeared to me that Danny Rancher had applied the conventional algorithm for converting a regular expression into an NFA with ϵ-transitions. The algorithm doesn't produce the simplest possible automata, but it does produce automata in a recognizably correct form. – MJD Apr 26 '12 at 12:04
@MarkDominus: Right, that is very likely. – Tara B Apr 26 '12 at 12:12

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.