# Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct?

(4c) For the alphabet {0, 1} construct ﬁnite 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

-
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

## 1 Answer

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.

-
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