Representing regular expressions with DFA state diagrams

Question

I have these regular expressions:

a) 0(10)*

b) a(b+c+d)

c) b*(aa*b*+ε)

I created these state diagrams for them:

Are they correct?

Answer 1

If I deciphered your writing correctly, this is what you wrote:

a) 0(10)*

Correct.

But two remarks:

• Clearly indicate which state is the starting state. It is common to use an incoming arrow for that, like you did in answer to (c).
• The rightmost two states are not really needed as they are indistinguishable from the first two states (at the top).

You could simplify to this:

b) a(b+c+d)

Not correct. There are these issues:

• a is not a valid input, so the second state should not be an accepting state.
• This first sink state lacks a transition for a. Once that is corrected, it becomes a state that is indistinguishable from the second sink, and so they could be merged
• And you should indicate which is the starting state

Correction:

c) b*(aa*b*+ε)

Correct!