DFA accepting strings with at least three occurrences of three consecutive 1's The problem states the following:


  Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with overlapping permitted.


I was able to come up "without overlapping" version as follows:



Regex of this DFA is (1+0)*111(1+0)*111(1+0)*111(1+0)*.
However this DFA does not accept 11111. This string should be accepted as the problem says overlapping of groups of three consecutive 1's is allowed. But I am not able to guess how do I do this. I feel I cannot do it with DFA as this will require to have some form of memory (for example, once I read 111, it should remember first occurrence of three consecutive 1's is read and also two consecutive 1's of next occurrence have already been read) which is not what DFA provides. Am I right with this? 

If not with DFA, can I do this with non deterministic finite automaton (NFA) or deterministic pushdown automaton (DPDA) or non deterministic pushdown automaton (NPDA)? Or this can be done only with Turing machine?
No, you don't need NFA (although it is equivalent to DFA) or PDA or Turing machine to solve this problem. It can be easily done with a DFA.

Lets number the states in given DFA in clockwise fashion starting from start state as Q0 to final state as Q9. First of all, it being a DFA, Q9 should have a self loop with label 1 as all possible transitions should be shown from all the states in a DFA. 

Now we need to add two states, lets name them Qa and Qb. The changes in the transitions to be made are as follows:-


Instead of having a 1 transition from Q2 to Q3, make a 1 transition from Q2 to Qa.
Instead of having a 1 transition from Q5 to Q6, make a 1 transition from Q5 to Qb.
Make a new 1 transition from Qa to Qb and a 0 transition from Qa to Q3.
Make a new 1 transition from Qb to Q9 and a 0 transition from Qb to Q6.


These changes in the provided DFA will allow it to satisfy given conditions. It simply counts input substring 1111 as two consecutive 111 and skips a step (of three intermediate states), increasing the count be 2.