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

    • 𝑞0: no "1" symbol encountered so far
    • 𝑞1: a single "1" symbol was encountered so far, followed by an even number of zeroes (if the next symbol is a "1" that would be acceptable)
    • 𝑞2: a single "1" symbol was encountered so far, followed by an odd number of zeroes (if the next symbol is a "1" that would not be acceptable)
    • 𝑞3: two "1" symbols were encountered so far, which have an even number of zeroes between them, and the second "1" is followed by any number of zeroes (only)
    • 𝑞4: either three "1" symbols were encountered, or two "1" symbols with an odd number of zeroes between them. This is the sink (input not accepted).

    The DFA diagram:

    enter image description here