1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ignore the bad words for the moment since they are easy to handle. Compute iteratively $a(k,x,c)$, which is the number of words of length $k$ whose last character $x$ is repeated $c$ times at the end, $k=0,1,\cdots, m$, $x\in\Sigma$, $c=1,2, \cdots, n$. $\endgroup$ – Apass.Jack May 8 at 2:36
  • $\begingroup$ While D.W.'s enlightening answer deals with the much general cases as well, my comment above shows athe straightforward algorithm by simple dynamic programming to count for the particular situation. $\endgroup$ – Apass.Jack May 8 at 13:26
1
$\begingroup$

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|$.

$\endgroup$
  • $\begingroup$ So you must actually count the number of words with an algorithm then? That is, there is no way to define a formula to get an answer using pure math? Just checking to make sure I understand. $\endgroup$ – Lokasa Mawati May 8 at 8:09
  • $\begingroup$ @LokasaMawati, I don't know. In the question you listed "algorithmically" as one of the options for a solution, so I assumed you'd be satisfied with an algorithm. $\endgroup$ – D.W. May 8 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.