Number of q-ary strings of length m which do not contain k consecutive zeros A finite q-ary-alphabet is given $$A_q = {0,1,2,...,q-1}.$$ Now I am considering the set of all finite strings over the alphabet $A_q$.
I am interested on the number $$N(m,k)_{A_q}$$ of strings of length $m$ which do not contain $k$ consecutive zeros. Is there a general formulary for this number? Or how can I determine $N(m,k)_{A_q}$?

Let me present another approach to this interesting problem, which will allow to get a closed expression for $N(m,k,q)$.
Let's consider a word of length $m$ from the binary alphabet $\{0,X\}$, having a total of $s$ zero's.

$$
\begin{array}{*{20}c}
   X &| &  {0,} & {0,} & {0,} &| &  X &| &  0 &| &  {X,} & X &| &  {0,} & 0 &| &  X  \\
   0 &| &  {1,} & {2,} & {3,} &| &  0 &| &  1 &| &  {0,} & {0,} &| &  {1,} & 2 &| &  0  \\
 \end{array} 
$$

Imagine to sequentially scan the word and count the number of consecutive zeros, resetting the counter
when the character is different from $0$, as in the exaple above.
Then we can bi-ject each word with an hystogram which has :
- $j$ bars;
- sum of the bars equal $s$;
- $m-s$ Xs.  
 
Now, the number of ways to compose $j$ bars, summing to $s$, and with a heigth going 
from $1$ to max $r$ is given by
$$
N_b (s - j,r - 1,j) = \text{No}\text{.}\,\text{of}\,\text{solutions}\,\text{to}\;\left\{ \begin{gathered}
  \text{0} \leqslant \text{integer}\;x_{\,j}  \leqslant r - 1 \hfill \\
  x_{\,1}  + x_{\,2}  + \; \cdots \; + x_{\,j}  = s - j \hfill \\ 
\end{gathered}  \right.
$$
which is expressed by
$$ \bbox[lightyellow] {  
\begin{gathered}
  N_b (s - j,r - 1,j)\quad \left| \begin{gathered}
  \;1 \leqslant \text{integer  }r \hfill \\
  \;0 \leqslant \text{integer}\;j \leqslant \text{integer }s \hfill \\ 
\end{gathered}  \right.\quad  =  \hfill \\
   = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{{s - j}}
{{r - 1}}\, \leqslant \,j} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  j \hfill \\
  k \hfill \\ 
\end{gathered}  \right)\left( \begin{gathered}
  s - 1 - k\,r \\ 
  s - j - k\,r \\ 
\end{gathered}  \right)}  \hfill \\ 
\end{gathered} 
 \tag{1} }$$
as explained in this post.  
Then we can dispose the $m-s$ (undistinguishable) X place-holders and the $j$ (distinguishable) bars by
- reserving $j-1$ X's as separators between consecutive $0$ blocks
- putting the remaining X's in any of the $j+1$ interstices,  thus in ${m-s+1} \choose{j}$ ways.  
Finally we can compose the Xs in $(q-1)^{m-s}$ ways. 
We shall pay attention to that  $j \leqslant s \leqslant \left\lceil {m/2} \right\rceil  $
Thus  the Number sought for, understood as
the number of words which contains max $k-1$ consecutive zeros (in one or more runs) will be
$$
\eqalign{
  & N(m,k,q)\quad \left| \matrix{
  \;1 \le {\rm integer  }k,q \hfill \cr 
  \;0 \le {\rm integer}\;m \hfill \cr}  \right.\quad  =   \cr 
  &  = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{0\, \le \,\,j\,\, \le \,s} {\left( \matrix{
  m - s + 1 \cr 
  j \cr}  \right)\sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,j} \right)} {\left( { - 1} \right)^i \left( \matrix{
  j \cr 
  i \cr}  \right)\left( \matrix{
  s - 1 - i\,\left( {k - 1} \right) \cr 
  s - j - i\,\left( {k - 1} \right) \cr}  \right)} } }  =   \cr 
  &  = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( \matrix{
  \left( {q - 1} \right)^{\,m - s} \quad  \cdot  \hfill \cr 
  \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m - s + 1} \right)} {\left( { - 1} \right)^i \left( \matrix{
  m - s + 1 \cr 
  i \cr}  \right)\sum\limits_{\left( {0\, \le } \right)\,\,j - i\,\,\left( { \le \,s - i} \right)} {\left( \matrix{
  m - s + 1 - i \cr 
  j - i \cr}  \right)\left( \matrix{
  s - 1 - i\,\left( {k - 1} \right) \cr 
  s - i\,k - \left( {j - i} \right) \cr}  \right)} }  \hfill \cr}  \right)}  =   \cr 
  &  = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m - s + 1} \right)} {\left( { - 1} \right)^i \left( \matrix{
  m - s + 1 \cr 
  i \cr}  \right)\left( \matrix{
  m - i\,k \cr 
  s - i\,k \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^i \left( \matrix{
  m - s + 1 \cr 
  i \cr}  \right)\left( \matrix{
  m - i\,k \cr 
  m - s \cr}  \right)} }  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^{\,i} \sum\limits_{0\, \le \,\,m - s\,\, \le \,m} {\left( \matrix{
  m - i\,k \cr 
  m - s \cr}  \right)\left( {\left( \matrix{
  m - s \cr 
  i \cr}  \right) + \left( \matrix{
  m - s \cr 
  i - 1 \cr}  \right)} \right)\left( {q - 1} \right)^{\,m - s} } }  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^{\,i} \left( {\left( \matrix{
  m - i\,k \cr 
  i \cr}  \right)q^{\,m - i\,k - i} \left( {q - 1} \right)^{\,i}  + \left( \matrix{
  m - i\,k \cr 
  i - 1 \cr}  \right)q^{\,m - i\,k - i + 1} \left( {q - 1} \right)^{\,i - 1} } \right)}  =   \cr 
  &  = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( {\left( \matrix{
  m - i\,k \cr 
  i \cr}  \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)}  - q^{\,m - k} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,\left( {m - k} \right)/k} {\left( {\left( \matrix{
  m - k - i\,k \cr 
  i \cr}  \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)}  =   \cr 
  &  = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m/k} \right)} {\left( {\left( \matrix{
  m - i\,k \cr 
  m - i\,\left( {k + 1} \right) \cr}  \right)\left( {{{1 - q} \over {q^{\,r + 1} }}} \right)^{\,i} } \right)}  - q^{\,\left( {m - k} \right)} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\,\left( { \le \,\left( {m - k} \right)/k} \right)} {\left( {\left( \matrix{
  \left( {m - k} \right) - i\,k \cr 
  \left( {m - k} \right) - i\,\left( {k + 1} \right) \cr}  \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)}  =   \cr 
  &  = M(m,\;k,\;q) - M(m - k,\;k,\;q) \cr} 
$$
where:
- in the first passage we use the trinomial revision $\left( \matrix{   s \cr    j \cr}  \right)\left( \matrix{   j \cr    n \cr}  \right) = \left( \matrix{   s \cr    n \cr}  \right)\left( \matrix{   s - n \cr    j - n \cr}  \right)$
- in the sum in $s$ we use $\sum\limits_k {\left( \matrix{   n \cr    k \cr}  \right)\left( \matrix{   k \cr    m \cr}  \right)y^{\,k} }  = \left( \matrix{   n \cr    m \cr}  \right)\left( {1 + y} \right)^{\,n - m} y^{\,m} $
obtainable from
$$
\left( {1 + y + y} \right)^{\,n}  = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} {\left( \matrix{
  n \cr 
  k \cr}  \right)\left( {1 + y} \right)^{\,k} y^{\,n - k} }  = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,n} \right)} {\left( \matrix{
  n \cr 
  k \cr}  \right)\left( \matrix{
  k \cr 
  j \cr}  \right)y^{\,n - j} } } 
$$
In conclusion
$$ \bbox[lightyellow] {  
\left\{ \matrix{
  M(m,k,q) = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m/k} \right)} {\left( {\left( \matrix{
  m - i\,k \cr 
  m - i\,\left( {k + 1} \right) \cr}  \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)}  \hfill \cr 
  N(m,k,q) = M(m,\;k,\;q) - M(m - k,\;k,\;q) \hfill \cr}  \right.\quad \left| \matrix{
  \;1 \le {\rm integer  }k,q \hfill \cr 
  \;0 \le {\rm integer}\;m \hfill \cr}  \right.
 \tag{2} }$$
and it can be verified that the above expression


*

*${\bbox[#dfd,5px]{\text{satisfies the recursion provided in *N. Shales*'s answer}}}$

*${\bbox[#dfd,5px]{\text{gives the terms of the z-transform provided in *Markus Scheuer*'s answer}}}$ .

