# Minimal-length strings which are substrings of no string in a given CFL

Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? In other words, given a CFG, $$G=(V,\Sigma ,R,S)$$, find a sequence of increasing-length strings $$E = \{e \in \Sigma^+ \mid \forall \sigma \in \mathcal{L}_G, e$$ is not a substring of $$\sigma\}$$.

• Do you have a proof that $E$ is guaranteed to be finite? Don't you want to specify $e \in \mathcal{L}_G$ rather than $e \in \Sigma^+$?
– D.W.
Sep 14 at 16:16
• $E$ may infinite, but in practice we only care about short strings $E \cap \Sigma^k$ where $k$ is some small number. Re: "Don't you want to specify $e \in \mathcal{L}_G$..." No. $e$ must be excluded from every substring of every string in $\mathcal{L}_G$. Sep 15 at 4:02

Here is a possible approach. Enumerate lengths in increasing order (length 0, length 1, length). For each length, enumerate all strings in lexicographic order, as follows.

Let's take length 4 as illustration. First, check whether any member of $$L$$ has any substring of the form a??? (where ? is a wildcard that can match any symbol). If not, then you can output aaaa, aaab, ..., azzz, then move on to checking whether any member of $$L$$ has any substring of the form b???. If yes, then move on to checking whether any member of $$L$$ has any substring of the form aa??. Repeat iteratively. In this way, you walk through possible prefixes in lexicographic order, in a breadth-first manner.

How do you check whether any member of $$L$$ has any substring of the form a???? This amounts to testing whether there is any string in both $$L$$ and $$\Sigma^* a \Sigma^3 \Sigma^*$$, i.e., whether $$L \cap \Sigma^* a \Sigma^3 \Sigma^* \ne \emptyset$$. Note that $$L$$ is context-free and $$\Sigma^* a \Sigma^3 \Sigma^*$$ is regular, so their intersection is context-free (and you can easily construct a PDA or context-free grammar for it using standard methods), and thus you can test whether it generates a non-empty language (using standard methods). Each check will take about $$O(|G| \ell^2)$$ time, where $$|G|$$ is the size of the context-free grammar $$G$$ for $$L$$ and $$\ell$$ is the length of strings you are enumerating.

• Thank you! Your algorithm seems to be viable, although I have not yet implemented it, because computing the intersection between a CFL and regular grammar is somewhat nontrivial in the presence of ε (cf. arxiv.org/pdf/2209.06809.pdf). I recently learned that Osorio and Navarro (2001) have another algorithm decides whether a given string is a substring of any string in a CFL, which considers not only the prefix, but also the infix and suffix cases. It seems somewhat more easy to implement: nokyotsu.com/me/papers/cic01.pdf Oct 3 at 3:31
• @breandan, I think it's easy to build a finite-state automaton that represents a regular language like $\Sigma^* a \Sigma^3 \Sigma^*$ (for instance, you can build a NFA, then convert to a DFA with the powerset construction; or you can construct a DFA directly), and then easy to intersect with a pushdown automaton for $L$.
– D.W.
Oct 3 at 6:24