dfanfa

State diagram of DFA with 5 states

Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F . (You may find it helpful first to find a 4-state NFA for the complement of F .)

how to come up with the solutions

Solution

  • Let's analyse this a bit. Some acccepted inputs would be:

    00000000000
100000
0010010
01100

    Notably, every input that has less than two "1" symbols is accepted. If there are two of them, the symbols between them are zeroes, and there should be an even number of those.

    The most important realisation is that there cannot be three or more "1" symbols in the input, as certainly the third one will violate the rule either by pairing it up with the first "1" or with the second "1". An example:

    1001001

    Although the middle 1 does not violate the constraint, it follows that the outer two do violate it (because the middle "1" is included in the count, making it odd).

    So we can have these states:

    The DFA diagram:

    enter image description here