Search code examples
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:

    • 𝑞0: did not encounter a 0 in the last two reads. This is also the start state, but it is not an accept state.
    • 𝑞1: the last symbol was 0, but not preceded by a 0. So it is not an accept state.
    • 𝑞2: the last two symbols were 01. An accept state.
    • 𝑞3: the last two symbols were 00. An accept state.

    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:

    • 𝑞0: The start state.
    • 𝑞1: The input started with 0, and the last symbol so far is a 0. This is not an accept state.
    • 𝑞2: The input started with 0, and the last symbol so far is a 1. An accept state.
    • 𝑞3: The input started with 1, so it cannot be accepted, no matter what follows. This is a sink.

    It looks like this:

    DFA 2