1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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^+$? $\endgroup$
    – D.W.
    Sep 14 at 16:16
  • $\begingroup$ $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$. $\endgroup$
    – breandan
    Sep 15 at 4:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – breandan
    Oct 3 at 3:31
  • $\begingroup$ @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$. $\endgroup$
    – D.W.
    Oct 3 at 6:24

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.