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:
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?
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:
0
in the last two reads. This is also the start state, but it is not an accept state.0
, but not preceded by a 0
. So it is not an accept state.01
. An accept state.00
. An accept state.It looks like this:
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:
0
, and the last symbol so far is a 0
. This is not an accept state.0
, and the last symbol so far is a 1
. An accept state.1
, so it cannot be accepted, no matter what follows. This is a sink.It looks like this: