L={w∈{0,1}∗∣every length-4 substring of w contains at most two 1's}
we will create 16 states to represent the four most recently-seen characters.
s1 = 0000, s2 = 0001, s2 = 0010, s3 = 0011
s4 = 0100, s5 = 0101, s6 = 0110, s7 = 0111
s8 = 1000, s9 = 1001, s10 = 1010, s11 = 1011
s12 = 1100, s12 = 1101, s14 = 1110, s15 = 1111
then we need to create binary tree,
reject states = { s7, s11, s13, s14, s15 } so these will be dead state
we are left with 11 accepting states and 1 dead state.
δ(si,0)=sj where j≡2i (mod 16) and
δ(si,1)=sj where j≡2i+1(mod 16)
It's complex but what can you expect from dfa with 12 states :p
