Krdytkyu

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the words of length $ngeq 0$ built from an alphabet $$mathcal{V}={0,1}$$ and the set $B={0^{k_1+1},1^{k_2+1}}$ of bad words, $k_1,k_2geq 0$, which are not allowed to be part of the words we are looking for.

We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.

According to the paper (p.7) the generating function $f(s)$ is

begin{align*}
f(s)=frac{1}{1-ds-text{weight}(mathcal{C})}tag{1}
end{align*}
with $d=|mathcal{V}|=2$, the size of the alphabet and $mathcal{C}$ the weight-numerator with
begin{align*}
text{weight}(mathcal{C})=text{weight}(mathcal{C}[0^{k_1+1}])+text{weight}(mathcal{C}[1^{k_2+1}])
end{align*}

We calculate according to the paper
begin{align*}
text{weight}(mathcal{C}[0^{k_1+1}])&=-s^{k_1+1}-text{weight}(mathcal{C}[0^{k_1+1}])(s+s^2+cdots+s^{k_1})\
text{weight}(mathcal{C}[0^{k_2+1}])&=-s^{k_2+1}-text{weight}(mathcal{C}[0^{k_2+1}])(s+s^2+cdots+s^{k_2})\
end{align*}
and get
begin{align*}
text{weight}(mathcal{C}[0^{k_1+1}])&=-frac{s^{k_1+1}}{1+s+cdots+s^{k_1}}=-frac{s^{k_1+1}(1-s)}{1-s^{k_1+1}}\
text{weight}(mathcal{C}[1^{k_2+1}])&=-frac{s^{k_2+1}}{1+s+cdots+s^{k_2}}=-frac{s^{k_2+1}(1-s)}{1-s^{k_2+1}}\
end{align*}

It follows
begin{align*}
text{weight}(mathcal{C})&=text{weight}(mathcal{C}[0^{k_1+1}])+text{weight}(mathcal{C}[1^{k_2+1}])\
&=-(1-s)left(frac{s^{k_1+1}}{1-s^{k_1+1}}+frac{s^{k_2+1}}{1-s^{k_2+1}}right)
end{align*}

$$ $$

We obtain the generating function
begin{align*}
f(s)&=frac{1}{1-ds-text{weight}(mathcal{C})}\
&=left(1-2s+frac{s^{k_1+1}(1-s)}{1-s^{k_1+1}}+frac{s^{k_2+1}(1-s)}{1-s^{k_2+1}}right)^{-1}tag{1}\
end{align*}

$$ $$

Example: $k_1=2,k_2=3$.

We consider the special case with the bad words $$B={0^{k_1+1},1^{k_2+1}}={000,1111}$$

We obtain from (1) with some help of Wolfram Alpha

begin{align*}
f(s)&=left(1-2s+frac{s^{3}(1-s)}{1-s^{3}}+frac{s^{4}(1-s)}{1-s^{4}}right)^{-1}\
&=frac{(1+s)(1+s^2)(1+s+s^2)}{1-s^2-2s^3-2s^4-s^5}\
&=1+2s+4s^2+7s^3+12s^4+color{blue}{21}s^5\
&qquad+36s^6+63s^7+109s^8+189s^9+328s^{10}+cdots
end{align*}

We see the coefficient of $s^5$ is $21$.
So, out of $2^5=32$ binary words of length $5$ there are $11$ invalid words containing subwords ${000,1111}$ which are marked blue in the table below.

begin{array}{cccc}
color{blue}{00000}&color{blue}{01000}&color{blue}{10000}&color{blue}{11000}\
color{blue}{00001}&01001&color{blue}{10001}&11001\
color{blue}{00010}&01010&10010&11010\
color{blue}{00011}&01011&10011&11011\
00100&01100&10100&11100\
00101&01101&10101&11101\
00110&01110&10110&color{blue}{11110}\
00111&color{blue}{01111}&10111&color{blue}{11111}\
end{array}

Any string fulfilling the wanted constraints has one of the following structures:
$$ 0^{a_1}1^{b_1}0^{a_2}1^{b_2}ldots qquad 1^{b_1}0^{a_1}1^{b_2}0^{a_2}ldots $$
with $a_ileq k_1, b_jleq k_2$ and $sum a_i+sum b_j = n$. Assume that we want to compute how many strings are there of the $0^{a_1}1^{b_1}0^{a_2}1^{b_2}0^{a_3}$ kind. They are given by the coefficient of $x^n$ in the product
$$ left(1+x+x^2+ldots+x^{k_1}right)^3cdotleft(1+x+x^2+ldots+x^{k_2}right)^2 = p_{k_1}(x)^3 p_{k_2}(x)^2$$
hence by accounting for all possible kinds, the answer is given by the coefficient of $x^n$ in
$$ sum_{rgeq 0}left(p_{k_1}(x)^r p_{k_2}(x)^{r+1}+p_{k_1}(x)^{r+1}p_{k_2}(x)^rright) =color{red}{frac{p_{k_1}(x)+p_{k_2}(x)}{1-p_{k_1}(x),p_{k_2}(x)}}.$$

Here is a comment showing how to compute the generating functions from
first principles. We may then continue as in the answer by
@MarkusScheuer.

Using $z$ for zero and $w$ for one we have the generating function

$$(1+z+z^2+cdots+z^{k_1})
sum_{qge 0} (w+w^2+cdots+w^{k_2})^q (z+z^2+cdots+z^{k_1})^q
\ times (1+w+w^2+cdots+w^{k_2}).$$

As we are only interested in the count we may write this as

$$(1+z+z^2+cdots+z^{k_1})
sum_{qge 0} (z+z^2+cdots+z^{k_2})^q (z+z^2+cdots+z^{k_1})^q
\ times (1+z+z^2+cdots+z^{k_2}).$$

This is

$$frac{1-z^{k_1+1}}{1-z}
left(sum_{qge 0} z^q frac{(1-z^{k_2})^q}{(1-z)^q}
z^q frac{(1-z^{k_1})^q}{(1-z)^q}right)
frac{1-z^{k_2+1}}{1-z}
\ = frac{1-z^{k_1+1}}{1-z} frac{1-z^{k_2+1}}{1-z}
frac{1}{1-z^2(1-z^{k_1})(1-z^{k_2})/(1-z)/(1-z)}
\ = frac{(1-z^{k_1+1})(1-z^{k_2+1})}
{1-2z+z^2-z^2(1-z^{k_1})(1-z^{k_2})}
\ = frac{1-z^{k_1+1}-z^{k_2+1}+z^{k_1+k_2+2}}
{1-2z+z^{k_1+2}+z^{k_2+2}-z^{2+k_1+k_2}}.$$

Some Maple code to verify these follows.

RL :=

proc(n, k1, k2)

    option remember;

    local ind, d, pos, cur, run, runs, res,

    zmax, wmax;



    res := 0;



    for ind from 2^n to 2*2^n-1 do

        d := convert(ind, base, 2);



        cur := -1; pos := 1;

        run := ; runs := ;





        while pos <= n do

            if d[pos] <> cur then

                if nops(run) > 0 then

                    runs :=

                    [op(runs), [run[1], nops(run)]];

                fi;



                cur := d[pos];

                run := [cur];

            else

                run := [op(run), cur];

            fi;



            pos := pos + 1;

        od;



        runs := [op(runs), [run[1], nops(run)]];



        zmax := max(seq(`if`(r[1] = 0, r[2], 0), r in runs));

        wmax := max(seq(`if`(r[1] = 1, r[2], 0), r in runs));



        if zmax <= k1 and wmax <= k2 then

            res := res + 1;

        fi;

    od;



    res;

end;



X :=

proc(n, k1, k2)

option remember;

local gf;



    gf :=

    (1-z^(k1+1)-z^(k2+1)+z^(k1+k2+2))

    /(1-2*z+z^(k1+2)+z^(k2+2)-z^(k1+k2+2));



    coeftayl(gf, z=0, n);

end;

You can set up a set of coupled recurrences. Let $A(k,n)$ be the number of acceptable $n$ bit strings that end with $k 0$'s and $B(k,n)$ be the number of acceptable $n$ bit strings ending with $k 1$'s. Then $A(k+1,n+1)=A(k,n)$ and $A(1,n+1)=sum_{i=0}^{k_2}B(i,n)$ and similarly for $B(k,n+1)$ Put the $A$'s and $B$'s into a column vector and you have a matrix that you multiply by the vector to increase the length of the string. You can diagonalize the matrix and find eigenvalues to find the asymptotic rate of growth.

Let me to begin with changing the $k$s to $k_0$ and $k_1$, so to help and remember their association with the values.

First step is to fix the total number of ones at , let say $0 leqslant q leqslant n$ (and the number of zeros is consequently fixed).
We know the total number of ways to obtain strings of length $n$ with $q$ ones, so we will at end accomodate for that.
Then your scheme is equivalent to many other combinatorial ones, e.g.
number of lattice paths from $(0,0)$ to $(n-q,q)$ with steps from $left{ {left( {1 ldots k_0 ,0} right),left( {0,1 ldots k_1 } right)} right}$.

After fixing the total number of $1$s, let now fix the number of $1$-blocks at $m$.
The number of $0$-blocks will be either $m$ (if the string starts and ends with different values), or $m-1$ (starts and ends with $1$) or $m+1$ (starts and ends with $0$).

The number of ways to arrange $q$ ones into $m$ blocks with no more than $k_1$ in each, is the number of compositions of $q$ in $m$ parts of max size $k_1$.
An expression for that can be derived from the answers to Rolling dice problem (re. to there for details), where we have:
$$
N_{,b} (s,r,m) = text{No}text{. of solutions to};left{ begin{gathered}
0 leqslant text{integer }x_{,j} leqslant r hfill \
x_{,1} + x_{,2} + cdots + x_{,m} = s hfill \
end{gathered} right.
$$
which can be expressed as
$$
N_{,b} (s,r,m)quad left| {;0 le {rm integers};s,r,m} right.quad = sumlimits_{left( {0, le } right),k,left( { le ,{s over r}, le ,m} right)} {left( { - 1} right)^{,k} left( matrix{
m cr
k cr} right)left( matrix{
s + m - 1 - kleft( {r + 1} right) cr
s - kleft( {r + 1} right) cr} right)}
$$
In our case, since the number of $1$s goes from $1$ to $k_1$, we shall replace $r$ with $k_1-1$ and $s$ with $q-m$.

Now we shall intersperse the $1$-blocks into the $0$-blocks "comb-to-comb".
The number of ways to make up the $0$-blocks follows the same formula, with the appropriate parameters.

Considering that the "starting-block($0$/$1$)-end-block($0$/$1$)" represents a partition of the considered strings,
it is not difficult to make up the four parts and conclude:
$$
begin{gathered}
N(k_{,0} ,k_{,1} ,n,q,m) = hfill \
= N_b (q - m,k_{,1} - 1,m)left( {N_b (n - q - m + 1,k_{,0} - 1,m - 1) + 2N_b (n - q - m,k_{,0} - 1,m) + N_b (n - q - m - 1,k_{,0} - 1,m + 1)} right) hfill \
end{gathered}
$$
In summing through $m$ and then $p$ (after multiplying by C(n,q)), note that in the $N_{,b} (s,r,m)$ formula, the bounds in the summation and in the parameters may be omitted (practically: stretched from $0$ to a suitable max),
because the binomials (as defined and as written), or the sum itself, are null for $m<k$ and $mr<s$, etc., being enough to ensure that $0 leqslant r$.

We consider the binary alphabet $V={0,1}$ and look for the number $g_n(k_1,k_2)$ of binary words of length $n$ which contain runs of $0$ with length at most $k_1$ and runs of $1$ with length at most $k_2$.

Words with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a binary alphabet is given by
begin{align*}
left(1-frac{2z}{1+z}right)^{-1}tag{1}
end{align*}

We replace occurrences of $0$ in a Smirnov word by one up to $k_1$ zeros to generate strings having runs of $0$ with length at most $k_1$
begin{align*}
zlongrightarrow z+z^2+cdots+z^{k_1}=frac{zleft(1-z^{k_1}right)}{1-z}tag{2}
end{align*}

We replace occurrences of $1$ in a Smirnov word by one up to $k_2$ ones to generate strings having runs of $1$ with length at most $k_2$
begin{align*}
zlongrightarrow z+z^2+cdots+z^{k_2}=frac{zleft(1-z^{k_2}right)}{1-z}tag{3}
end{align*}

We substitue (2) and (3) in (1) and obtain

begin{align*}
&left(1- frac{frac{zleft(1-z^{k_1}right)}{1-z}}{1+frac{zleft(1-z^{k_1}right)}{1-z}}
- frac{frac{zleft(1-z^{k_2}right)}{1-z}}{1+frac{zleft(1-z^{k_2}right)}{1-z}}right)^{-1}\
&qquad=frac{(1+z)left(1-z^{k_1}right)left(1-z^{k_2}right)}{1-z+2z^2-left(z^{k_1+1}+z^{k_2+1}right)(1+z)-z^{k_1+k_2+2}(1+3z)}tag{4}
end{align*}

Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain from (4) the number of wanted words as
begin{align*}
color{blue}{g_n(k_1,k_2)
=[z^n]frac{(1+z)left(1-z^{k_1}right)left(1-z^{k_2}right)}{1-z+2z^2-left(z^{k_1+1}+z^{k_2+1}right)(1+z)-z^{k_1+k_2+2}(1+3z)}}tag{5}
end{align*}

Example: $n=5,k_1=2,k_2=3$.

We consider the special case with words of length $5$ containing runs of $0$ with length at most $2$ and runs of $1$ with length at most $3$

We obtain from (5) with some help of Wolfram Alpha

begin{align*}
sum_{n=0}^infty g_n(k_1,k_2)z^n&=frac{(1+z)(1-z^3)(1-z^4)}{1-z+2z^2-(z^3+z^4)(1+z)-z^7(1+3z)}\
&=frac{(1+z)(1+z^2)(1+z+z^2)}{1-z^2-2z^3-2z^4-z^5}\
&=1+2z+4z^2+7z^3+12z^4+color{blue}{21}z^5+36z^6+63z^7+cdots
end{align*}

We see the coefficient of $z^5$ is $21$.
The $21$ valid words are
$$
begin{array}{cccc}
00100&01001&10010&11001\
00101&01010&10011&11010\
00110&01011&10100&11011\
00111&01100&10101&11100\
&01101&10110&11101\
&01110&10111&
end{array}
$$