This question is about an extension of a language discussed in this question.We define the $r$-skip $k$-distinct language as follows:$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \forall i\neq j\in [rk],i=j \mod r\implies \sigma_i \neq\sigma_j\}$$That is, the set of letters whose distance is a multiplication of $r$ are different.This language is finite and therefore regular. Specifically, if $|\Sigma|=n$, then $|L_{r,k}|=$$({n\choose{k}}\cdot k!)^r$.For $r=1$ we get the language $L_{k-distinct}$ defined in the linked question.A natural NFA build for $L_{r,k}$ uses the color coding scheme and for a $(|\Sigma|,k)$-perfect hashing family $\mathcal F$ (i.e. mapping the letters into $k$ indices) selects a hash function $f\in \mathcal F$ by an epsilon transition and then verifies that each set of letters $\Sigma_i = \{\sigma_j|i=j \mod r\}$ is distinct.Such perfect hashing family build of size $O(e^{k+\log^3 k}\cdot n\log n)$ is knownThe resulting automaton is of size $O((2e)^{r(k+O(\log^3 k))}\cdot n\ \text{polylog}\ n)$, which is the same as we would get for $L_{1,rk}$ (which is $L_{rk-distinct}$) by using the same approach.(The reason for this size, at least in a naive build, is that the automaton state have to encode which of the $k$ colors we've seen for each of the $r$ letter sets). A more careful build would give $O(4^{r(k+O(\log^2 k))}\cdot n\ \text{polylog}\ n)$ sized automaton (same goes for $L_{1,rk}$).This sounds wasteful, as a lot fewer comparison are needed as $r$ grows larger (and $rk$ is constant).What is the smallest automaton we can build for $L_{r,k}$?
Bounds on the size of NFA for $r$-skip $k$-distinct language
fl.formal languages;regular language;upper bounds;nondeterminism