2
$\begingroup$

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

  • 0
    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.2012-04-26

1 Answers 1

1

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.

  • 0
    @MarkDominus: Right, that is very likely.2012-04-26