We add the substring $1111$ as prefix to every $w\,\epsilon \, L$ (to fullfill the below assumption for characters at index 0,1,2)
The state of an automata which checks if a word $w\, \epsilon \,L$, denotes a substring of length $4$ ending at the current character. So, if we are at index $i$ of the string it denotes that the string upto this index is valid and when we make a transition for index $i+1$ there is only one substring that we have to check for this string to be valid $i.e$ the substring of length $4$ ending at the $\left ( i+1 \right )$th index.
$q$d is the dead state for the automata and all the other states are final states, $q$0 is the start state.
$q$0 $= \, 1111$ , $q$1 $= \, 1110$ , $q$2 $= \, 1100$ , $q$3 $= \, 1001$ , $q$4 $= \, 0011$ , $q$5 $= \, 1101$ , $q$6 $= \, 1010$
$q$7 $= \, 1011$ , $q$8 $= \, 0110$ , $q$9 $= \, 0101$ , $q$10 $= \, 0111$ , $q$d $= \, \left \{ 0010,1000, 0100, 1001\right \}$
The transition table for the automata is
| State |
0 |
1 |
| $q$0 |
$q$1 |
$q$0 |
| $q$1 |
$q$2 |
$q$5 |
| $q$2 |
$q$d |
$q$3 |
| $q$3 |
$q$d |
$q$4 |
| $q$4 |
$q$8 |
$q$10 |
| $q$5 |
$q$6 |
$q$7 |
| $q$6 |
$q$d |
$q$9 |
| $q$7 |
$q$8 |
$q$10 |
| $q$8 |
$q$2 |
$q$5 |
| $q$9 |
$q$6 |
$q$7 |
| $q$10 |
$q$1 |
$q$0 |
| $q$d |
$q$d |
$q$d |
For Example :
0010 : $q$0 $\rightarrow$ $q$1 $\rightarrow$ $q$2 $\rightarrow$ $q$3 $\rightarrow$ $q$d
101001 : $q$0 $\rightarrow$ $q$0 $\rightarrow$ $q$1 $\rightarrow$ $q$5 $\rightarrow$ $q$6 $\rightarrow$ $q$d
0011 : $q$0 $\rightarrow$ $q$1 $\rightarrow$ $q$2 $\rightarrow$ $q$3 $\rightarrow$ $q$4
Correct me if I'm wrong
