Search code examples
finite-automatacomputation-theorydfanfa

Pair of Zeros separated by 1's NFA?

I'm working on a language L = { every pair of zeros is separated by 1's that's of length 4i, i>=0 }

e.g. 110011110 should be accepted because the first two zeros are separated by nothing. Then the next pair is separated by 4 ones.

Here's my attempt for the NFA, anything missing?

enter image description here

Solution

  • We can use Myhill-Nerode directly to derive a minimal DFA for this language. The reasoning is straightforward.

    1. e, the empty string, can be followed by any string in L to get to a string in L.
    2. 0 can be followed by 1* or by (1^4i)L to get to a string in L.
    3. 1 can be followed by L to get to a string in L. This means it is indistinguishable from the empty string. That also means we don't need to worry about longer strings that start with 1, since they will be covered by shorter strings that don't start with 1.
    4. 00 can be followed by the same stuff as 0 can, so it is indistinguishable. This also means we don't need to worry about longer strings that start with 00, since they are handled by shorter strings that don't.
    5. 01 can be followed by 1* or 111(1^4i)L to get to a string in L.
    6. 10, 11 can be ignored as they start with 1 (see 3)
    7. 000, 001 can be ignored as they start with 00 (see 4)
    8. 010 cannot be followed by anything to get a string in L. We can also ignore anything that starts with this since it can't lead to a string in L.
    9. 011 can be followed by 1* or 11(1^4i)L to get a string in L.
    10. 100, 101, 110, 111 can be ignored as they start with 1 (see 3)
    11. 0000, 0001, 0010, 0011 can be ignored as they start with 00 (see 4)
    12. 0100, 0101 can be ignored since they start with 010 (see 8)
    13. 0110 cannot be followed by anything to get to a string in L so is indistinguishable from 010.
    14. 0111 can be followed by 1* or 1(1^4i)L to get a string in L.
    15. 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 can all be ignored since they start with 1 (see 3)
    16. The only string of length four distinguishable from shorter strings was 0111; 01110 is indistinguishable from 010 in that nothing leads it to a string in L, and 01111 is indistinguishable from 0 in that it can be followed by 1* or (1^4i)L to get to something in L.

    This may seem like a lot of work, but it was a pretty simple exercise. We can go back through and list our complete set of shortest-length distinguishable strings:

    1. e, from point 1 above
    2. 0, from point 2 above
    3. 01, from line 5 above
    4. 010, from point 8 above
    5. 011, from point 9 above
    6. 0111, from point 14 above

    To write down a DFA, we need one state for each of these shortest-length distinguishable strings. The transitions from the state corresponding to string x will lead to states corresponding to strings formed by concatenating input symbols to x. So:

                ___________________________
            |                         ^
        0   V  1       1        1     | 1
--->(e)--->(0)--->(01)--->(011)--->(0111)
    \_/    \_/      | 0     | 0       | 0
     1      0       |       V         V
                    |<-----------------
                    V
                    (010)
                    \___/
                     0,1
    1. e is the initial state.
    2. the state for e loops to itself on 1 since e.1 = 1 and 1 is indistinguishable from e. Indistinguishable strings lead to the same state in a minimal DFA.
    3. the state for e goes to the state for 0 on 0 since e.0 = 0 and 0 is distinguishable from all strings of the same or shorter length.
    4. state 0 leads to state 01 leads to state 011 leads to state 0111 on 1s, since 0111 = 011.1 = 01.1.1 = 0.1.1.1 and these are all distinguishable from strings of the same or shorter length.
    5. 0111 leads to 0 on 1 since 0111.1 = 01111 which is indistinguishable from 0.
    6. states 0, 01, 011 and 0111 lead to state 010 on 0 since 0.0 = 00, 01.0 = 010, 011.0 = 0110 and 0111.0 = 01110 are indistinguishable from 010.
    7. 010 leads to itself on all inputs since nothing can be added to it to get a string in L, so the same is true for any concatenation with this at the front.

    Now that we have the structure, we simply have to look at each state and say whether its canonical string is in L. If so, the state is accepting; otherwise, it is not.

    1. e is in L, so (e) is accepting.
    2. 0 is in L, so (0) is accepting.
    3. 01 is in L, so (01) is accepting.
    4. 010 is in L, so (010) is not accepting.
    5. 011 is in L, so (011) is accepting.
    6. 0111 is in L, so (0111) is accepting.

    This completes the derivation of the minimal DFA for L.