The negation of the statement:
( >=3 consecutive zero's OR >=4 consecutive ones )
is:
(<3 consecutive zeros AND <4 consecutive ones)
Now, lets find out the number of strings for the negation part.
We set up a recurrance relation.
ZER(n)
= strings of length 'n' starting with 0 or 00 and containing less than 3 zeros
= (starting is single zero).ONE(n-1) + (starting is 00).ONE(n-2)
ONE(n)
= strings of length 'n' starting with 1 or 11 or 111 and containing less than 4 ones
= (starting with 1).ZER(n-1) + (starting with 11).ZER(n-2) + (starting with 111).ZER(n-3)
Now, we set up the base conditions:
ZER(0)=1
ZER(1)=1 (i.e.the string 0)
ZER(2)=2 (i.e. the string 01 and 00)
ONE(0)=1
ONE(1)=1 (i.e the string 1)
ONE(2)=2 (i.e the string 10 and 11)
Now, let the total strings of length 'n' containing less than 3 consecutive zeros and less than 4 consecutive ones
= T(n)
$\therefore$ T(n) = ZER(n) + ONE(n)
Now, we start calculating the values one by one.
T(3) = ZER(3) + ONE(3) ............(1)
ZER(3) = ONE(2) + ONE(1) = 3
ONE(3) = ZER(2) + ZER(1) + ZER(0) = 2+1+1 = 4
(Note: If we take ZER(0)=0 then ONE(3)=3 which gives wrong answer. If I take ZER(0)=0 then the string 111 which will come under ONE(3) as ZER(0) will be counted as 0 and not 1).
$\therefore$ From (1), T(3) = 3+4 = 7
Similarly,
T(4) = ZER(4) + ONE(4) = 5 + 6 = 12
T(5) = ZER(5) + ONE(5) = 9 + 10 = 21
T(6) = ZER(6) + ONE(6) = 16 + 17 = 36
T(7) = ZER(7) + ONE(7) = 27 + 30 = 63
T(8) = ZER(8) + ONE(8) = 47 + 52 = 109
Now, Strings containing either 3 consecutive zeros or 4 consecutive ones
= total bit strings of length 8
- strings containing less than 3 consecutive zeros and less than 4 consecutive ones
= 28 - T(8)
= 256 - 109
= 147