How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

Question

If I have the following system, I am wondering how to calculate the number of valid strings it contains.

The system is something like this, which can have arbitrary variations.

• Only consists of an alphabet $\Sigma$.
• It can't spell any words in a blacklist word list $\rho$.
• It can't have more than $n$ characters of the same type in a row.
• Every word $\omega$ it generates is no more than $m$ in length.

So for example, we might have this system:

• $\Sigma = (a, b, c, d, e, f, g, h)$
• $l = \texttt{len}(\Sigma)$
• $\rho = (\texttt{bed},\texttt{fad},\texttt{dad},\texttt{bead},\texttt{deed},\texttt{fade})$
• $n = 3$ (so can't match /aaaa|bbbb|cccc|dddd|eeee|ffff|gggg|hhhh/)
• $m = 20$

Say we have a random number generator, which uses a radix algorithm to convert it into a string using the characters in the alphabet $\Sigma$. The thing is, this random number generator might generate strings like the following, which we just have to drop and forget, then try generating another one until we get one that matches the constraints. Don't know of a better way to do that, but that's beside the point. So it might generate these ones, which are invalid.

afbcdeabeadbeaaaadaf
[bead and aaaa]
bedddddagheadfffeeee
[bed and dddd]

So the question is, how do I calculate how many strings are invalid? I know how to calculate the possible strings given the constraints, that is simply:

$$z = l^m = 8^{20}$$

I don't know how to calculate the number of strings that are invalid though, in a general way (so I can change the value of $m$, $n$, $\Sigma$, or $\rho$). Wondering how to formulate this problem mathematically or algorithmically so that I can figure out that "there are x number of invalid strings", and so I can calculate:

$$y = z - x$$

to get the total amount of possible strings given the constraints.

Answer 1

The language of valid strings is regular. Build a DFA to recognize the language, then use standard techniques to count the number of words accepted by the DFA (see Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038).

How do you build a DFA to recognize the language? Via a product construction. Let $L_a$ denote the set of all words that don't have $n+1$ $a$'s in a row, and let $L_\rho$ denote the set of all words that aren't in the blacklist. Then your language is $\Sigma^{\le m} \cap L_\rho \cap L_a \cap L_b \cap \cdots$. You can easily build DFAs for each of the individual languages, and then use the product construction to build a DFA for their intersection.

Warning: the size of the DFA can potentially blow up exponentially in $|\Sigma|$. However, this will remain polynomial in $n$, $m$, and $|\rho|$.