Search code examples
finite-automatacomputation-theorynon-deterministicautomata-theory

Construct nfa occuring strings over {0,1} such that some two 0's are seperated by a string of length 4i, i>=0

The given image has my solution to the question, which is wrongI am trying to solve this problem by first designing an NFA for a string of length 4i, as this is in the form of 0(mod 4).

Number of states = 4 and I just added 2 other states, one on each end of this design, and made a transition on 0, now number of states=6. My solution is wrong when I tried checking. Can someone pls explain where I am going wrong?

Solution

  • The high-level design for this NFA is correct, there are just a few missing details. One strategy I've found helpful when designing NFAs is to first start by coming up with a set of test cases or test strings. That is, if I were writing a program to check whether or not a string met these certain properties, what strings would I test? What would the edge cases be? These can help you spot patterns when you're first designing the NFA and you can use them to check your work afterwards.

    For example, here are some of the test cases I would check for this problem: 

    00              \\ i = 0
010100          \\ i = 1
0101011010      \\ i > 1, handles lengths of larger multiples of 4
011110, 000000  \\ it shouldn't matter what's in between the two 0s
111010100       \\ can have anything before the two 0s 
010100111       \\ can have anything after the two 0s
... etc...

    You should consider these two in particular:

    • 000000 - in the loop of your NFA that's checking whether or not the length of the string in between the two 0s is a multiple of 4, there is no restriction on the contents of this string. Specifically, there's no reason that the first character of this string cannot be a 0 (the transition from q1 to q5).
    • 010100111 (and/or 0101001110, 0101000) - these are all examples of strings where we have two 0s separated by a string of length 4i, followed by some other characters. These strings should also be accepted by your NFA but currently are not - remember that an NFA accepts if it finishes in an accepting state, and that if an NFA needs to make a transition and no transition exists, it dies and that path rejects.

    Do you see what modifications you can make to address these problems?