1
$\begingroup$

Background

I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not exceed a given length $N$. My algorithm cannot fail partway and backtrack, i.e. it can't just generate a string from $L$ normally and raise an error / start over / return an incomplete result when hitting the length limit. It must generate a valid string each time, and it must be able to produce any string in the set $\{s \in L \mid \lvert s \lvert \leq N\}$.

My task can be reduced to a slightly different problem that I can define more formally.

Formal description

Given some string $s \in L, \lvert s \lvert \leq N$, define the function $\mathrm{alt}(s, i, L) = \left \{c \in \Sigma \mid \exists t \in \Sigma^*: s_{[0:i]}ct \in L, \lvert s_{[0:i]}ct \lvert \leq N \right\}$. In other words, $\mathrm{alt}(s, i, L)$ represents the set of possible symbols that could be placed after the first $i$ symbols of $s$, that still result in a valid prefix of a string from $L$, where the completed string is at most $N$ symbols.

Given some grammar or description $G$ that generates $L$, I am interested in efficient algorithms of the below form:

alt_generator = AltGenerator(G, N)
alt_list = []
for i in range(0, len(s)):
    alt_list.append(alt_generator.get_alt())
    alt_generator.step(s[i])

such that by the end of the loop we obtain $\mathrm{alt\_list} = [ \mathrm{alt}(s, i, L) \mid 0 \leq i < \lvert s \lvert ]$.

I was able to find an algorithm with time complexity $O(N)$ if $G$ is a regular expression, and time complexity $O(N^3)$ if $G$ is a context-free grammar, using techniques similar to those mentioned here.

Main question: If $G$ is a deterministic context-free grammar (DCFG), is there an algorithm of the above form that is more efficient than $O(N^3)$?

Since DCFG's can be parsed in linear time, I suspect it might be possible. However, I cannot find a way to take advantage of the determinism of the grammar, and I can't think of theorems I can use to prove / disprove the existence of a linear time algorithm.

My work so far

The algorithm I found for regular expressions and generic CFG's works by first converting the grammar into an NFA or PDA, then taking the product construction with another NFA that accepts any string up to length $N$. We can incrementally add new states for each symbol in $s_{[0:i]}$, and then check all symbols in the alphabet $\Sigma$ to determine which symbols can be added without making the final accept state unreachable. The updates at each step can be optimized to $O(1)$ for regular expressions, but otherwise they will be $O(N^2)$ using the algorithm in the above link.

If $G$ is a DCFG, then we can obtain a DPDA from the product construction. It's possible to simply simulate the transition of the DPDA for all possible symbols added after $s_{[0:i]}$. But I don't think it's easy to know whether the DPDA has entered a dead end or not. We need an algorithm to find if a DPDA still can reach an accepting configuration from a given state, one that's better than $O(N^2)$ to beat my current method. I didn't find references of a special efficient algorithm for DPDA's. For general PDA's I only found my method, or the method of converting to a CFG then checking if it is equivalent to the empty grammar, which is even worse.

The product construction also lets us create a DPDA that directly recognizes $\{s \in L \mid \lvert s \lvert \leq N\}$. This could be converted back into a CFG, and then converted to a different CFG that generates all prefixes of $L$. Finally, we can try all symbols in the alphabet to see if they can be appended to $s_{[0:i]}$ to create a valid prefix. But this is a very complicated process and I suspect it will not be better than $O(N^3)$. Yes, it's true that the DPDA can be constructed into a DCFG. Even the second conversion that generates the prefix language could potentially be made a DCFG according to here. I think it's even possible to skip the second conversion if we can build an LR parser for the first DCFG, based on here. But the size of this grammar is not constant in $N$, according to here the normal conversion process creates a CFG of size $O(N^3)$. I don't know if the conversion is more efficient for a DPDA.

Maybe there's a way to directly create a DCFG that recognizes $\{s \in L \mid \lvert s \lvert \leq N\}$, without creating a pushdown automaton first? It's possible to make a parser for the new DCFG that fails on the first symbol that cannot lead to a valid string. If this new DCFG is small, this should lead to an algorithm better than $O(N^3)$. Alas, I cannot find a way to directly build the DCFG for $\{s \in L \mid \lvert s \lvert \leq N\}$ given the DCFG for $L$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.