The question can be described in the following way: 


Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$.


I have a string that is composed of a concatenated series of $n$ instances of $w\_i$ chosen randomly(uniformly, independently) from $\mathcal{L}$. I want to find the number of non-overlapping occurrences of another word $W$ over the same alphabet, in that string. Non-overlapping means that occurrences must have distinct positions ("11" occurs once in "111"). 


Are there standard tools to handle this? It is a bit similar to type 2 binominal distribution, but not exactly the same. 


In my case, I have $$\mathcal{L}=\{a,ab\}$$  

And $$W=aba$$


Thanks!



Distribution of non-overlapping words in randomly generated text
I'm not sure about the general case, but your particular one is relatively easy.


Let $r$ be a word composed of $n$ instances of $u:=a$ and $v:=ab$ chosen randomly.


We notice that each non-overlapping occurrence of $W$ in $r$ starts with an instance of $v$, unless this instance comes immediately after an odd number of other instances of $v$ or ends $r$.
It follows that if we decompose $r$ into copies of $u$, $vu$, $vv$, and possibly a single $v$ at the very end (notice that such a decomposition is unique), then the number non-overlapping occurrences of $W$ in $r$ equals the total number of $vu$ and $vv$ in the decomposition.


From the probabilistic perspective, each $u$ (or $v$ at the end) appears in the decomposition with probability $\frac{1}2$, while the probability of each of $vu$ and $vv$ is $\frac{1}{4}$. 
At the same time, $u$ and $v$ contribute $1$ to the number of instances (i.e., towards $n$), while $vu$ and $vv$ contribute $2$ here.


It follows that the probability $p\_{n,k}$ to observe exactly $k$ non-overlapping occurrences of $W$ in $r$ equals the coefficient of $x^ny^k$
in
$$
\sum\_{i=0}^{\infty} (\frac{1}{2}x+\frac{1}{4}x^2y+\frac{1}{4}x^2y)^i (1+\frac{1}{2}x) = \frac{1+\frac{1}{2}x}{1-\frac{1}{2}x-\frac{1}{2}x^2y},$$
where the powers of $x$ account for the number of instances of $u,v$ in $r$, while the powers of $y$ account for the number of non-overlapping occurrences of $W$.


Extracting the coefficient of $y^k$, we get that that $p\_{n,k}$ equals the coefficient of $x^n$ in
$$\frac{1+\frac{1}{2}x}{1-\frac{1}{2}x}\left(\frac{\frac{1}{2}x^2}{1-\frac{1}{2}x}\right)^k,$$
which further implies that
\begin{split}
p\_{n,k} &=\frac{1}{2^k}\left(-\frac{1}{2}\right)^{n-2k}\binom{-(k+1)}{n-2k}+\frac{1}{2^{k+1}}\left(-\frac{1}{2}\right)^{n-2k-1}\binom{-(k+1)}{n-2k-1}\\
&=\frac{1}{2^{n-k}}\binom{n-k}{n-2k}+\frac{1}{2^{n-k}}\binom{n-k-1}{n-2k-1}\\
&=\frac{1}{2^{n-k}}\binom{n-k}{k}\frac{2n-3k}{n-k}.
\end{split}


