regular-languagefinite-automatadfaautomata-theory

Are my DFA's correct? (arbitrary long sequence of 0's and 1's)


For my exercise I'm supposed to create two DFA's.

The task specifically is:

Construct a DFA over the alphabet Σ={1,0} accepting the following regular languages.

a) An arbitrary long sequence of zeros and ones that ends with a zero followed by a zero or a one.

b) An arbitrary long sequence of zeros and ones that starts with a zero and ends with a one.

These are my DFA's:

a)

b)

They are nearly the same (except the accepting states) and I wanted to know if they are correct? Maybe I'm missing something?

I tried to draw two DFA's. They seem to accept the languages but I think also some more... is that avoidable? Or still correct?


Solution

  • First DFA

    Your DFA for the first language has only accept states, and accepts all sequences of 0 and 1. For instance, it accepts any string that has no zeroes, yet we need the one-but-last input symbol to be a zero...

    For the first language you'll need four states:

    It looks like this:

    DFA 1

    Second DFA

    Your DFA for the second language will accept "1", which does not obey the rule that it should start with "0". Also, if an input starts with "1" there is nothing that can follow in that input that can make it accepted, so you need a "sink", i.e. a state that is not an accept state and from which you cannot transition to another state.

    Again, we need four states:

    It looks like this:

    DFA 2