How to approach DFA construction with substring constraints? We have to construct a DFA over the alphabet 0 and 1 for:


  Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.


I haven't reached to regular expression in the book which I am using. I am currently in unit 2 and regular expressions is from unit 3.
Use the state of the automaton to "remember" enough information about the string that you've seen so far to allow you to determine whether the string you've read is in the language. This is true essentially independently of the language you're trying to recognize.