Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L \mid \lvert s \lvert \leq N \}$? In other words, an algorithm that creates a DCFG whose language is the set of valid strings from $L$ that are under a certain length $N$.

For the algorithm, what would be the size of $G_N$ in terms of $N$? I'm especially interested if there are algorithms that result in $G_N$ of size $O(N)$ or even $O(N^2)$.

I'm also interested if there are arguments, perhaps heuristic ones, for a lower bound on the size of $G_N$. Because DCFG's can be parsed efficiently, I suspect $O(N)$ is possible, but maybe I'm wrong and adding the length limit forces a worst case of $O(N^3)$.

  • $\begingroup$ If you convert $G$ to a DPDA (e.g., a LR(1) parser), then add a counter to the state of the DPDA, then convert the DPDA back to a CFG, does this achieve a CFG of size $O(N)$? $\endgroup$
    – D.W.
    Commented Mar 14 at 8:11
  • $\begingroup$ @D.W. Great to see you, I see this approach is related to your algorithm here, which I found really helpful elsewhere! However, I think the conversion from DPDA to CFG would make the grammar much bigger than $O(N)$, I only found mentions of a $O(N^3)$ conversion method. I don't know if DCFG's are smaller if converted the same way. $\endgroup$
    – Jerry Ding
    Commented Mar 14 at 8:31
  • $\begingroup$ Is the grammar also of size $\Omega(N)$? In the parsing literature, we often see that the size of the grammar is assumed to be in $O(1)$. $\endgroup$ Commented Apr 17 at 15:38
  • $\begingroup$ @HermannGruber Yeah, the size of the original $G$ grammar is not dependent on $N$ $\endgroup$
    – Jerry Ding
    Commented Apr 18 at 4:24

2 Answers 2


A partial answer: The number of productions needed by a (not necessarily deterministic) context-free grammar generating $L\cap \Sigma^{\le N}$ in the worst case is $\Theta(N^2)$, as given in Theorem 4 of

W. Bucher, H.A. Maurer, K. Culik, D. Wotschke, Concise description of finite languages, Theoretical Computer Science 14(3), 1981, pp. 227-246.

For convenience, we reproduce the construction and the outline of the lower bound. Given a context-free grammar $G=(V,\Sigma, P, S)$ in Chomsky normal form, for every variable $A\in V$, we introduce variables $A^{(1)}, \ldots A^{(N)}$ and productions

  • $A^{(i)}\to B^{(i-k)}C^{(k)}$, for $i=2$ to $n$ and $k=1$ to $i-1$ and all productions of type $A\to BC$,
  • $S^{(i)}\to S^{(i-1)}$, for $i=2$ to $n$
  • $A^{(1)}\to a$ for all productions of type $A\to a$ or $S \to \varepsilon$.

For correctness proof, see the proof in the paper.

I assume that if the original context-free grammar is deterministic, then so is the above constructed grammar (I haven't checked carefully though, for example the conversion to Chomsky normal form).

For the lower bound, they prove that the language $U_n = \{\,a^k b^k ca^\ell b^\ell d a^mb^m \mid 0 \le k+\ell+m \le n \,\}$ requires $\Omega(n^2)$ context-free productions. As noted in the comments, the language $U := \bigcup_n U_n$ is a deterministic context-free language, so this gives a quadratic lower bound for the problem asked by the OP.

More precisely, they prove that the language $\widehat{U}_n = U_n \cap \Sigma^n$ is incompressible by context-free grammars, in the sense that any context-free grammar (not necessarily in any normal form) generating this finite set has at least as many context-free productions as there are words in the language (Theorem 1).

Also, they show that for a finite language $L$ whose words are of length at most $n$, the required number of context-free productions for generating $L \cap \Sigma^n$ is a lower bound for the required number of context-free productions for generating $L$ (Lemma 2.2).

  • $\begingroup$ Great! The lower bound is a very interesting result, I can see how this $U_n$ language is deterministic too $\endgroup$
    – Jerry Ding
    Commented Apr 23 at 6:30
  • $\begingroup$ Concerning whether the grammar is “deterministic”, first, as discussed in comments on the other question by the OP (cstheory.stackexchange.com/q/54051), it’s highly unclear what, if anything, a “DCFG” means. Certainly the definition the OP found in a random post by some anonymous guy on the cs site is nonsensical. DCFL are normally defined as languages accepted by DPDA, not by any sort of grammars. It appears though that in some literature, a “deterministic CFG” is taken to be a synonym of “$\mathrm{LR}(k)$ grammar for some $k$”. Having said that, the grammar constructed here is ... $\endgroup$ Commented Apr 23 at 8:32
  • 1
    $\begingroup$ ... most unlikely to be deterministic under any reasonable definition of a “deterministic grammar”, since parsing the language according to this grammar in effect requires you to guess in advance the exact lengths of the subwords that will be generated by the nonterminals on the right-hand side whenever you are applying an $A\to BC$ rule. The construction preserves the unambiguity of the grammar, though. $\endgroup$ Commented Apr 23 at 8:36
  • $\begingroup$ @EmilJeřábek thank you, I have to admit that I didn't think too hard about determinism. $\endgroup$ Commented Apr 23 at 10:36
  • 1
    $\begingroup$ @JerryDing also from my understanding, a deterministic CFG probably refers to $LR(k)$ grammar for some $k$. Please make this explicit in the question if this is meant. $\endgroup$ Commented Apr 23 at 10:39

Here is one algorithm:-

Step 1: Convert the grammar to CNF. This should take time O(square of no. Of productions)

Idea: The basic idea is to subscript each use of non terminals. For each variable X, Xi on the head of a rule denotes that the substitution of this rule is to match ith letter in the input word.

Step 2: For start rule, S->AB, we shall call subscript(S->AB,0).

The procedure subscript is described as (for simplicity suppose you are adding rules to a new grammar so there is no need to handle removal of old rules):-

        if(Y and Z are variables){
            return {cur+1};
        // Means it is of the form X->a
        // Add the rule X<sub>cur</sub> -> a
        return {cur+1};
    for each production of form Y-> WU{
        // W or U can be epsilon or terminal as well, but not together
        new_cur = subscript(Y->WU,cur);
    for each production of form Z->PQ{
        // P or Q can be epsilon or terminal also, but not together
        for elem in list{
            new_cur = subscript(Z->PQ,elem);
            // Add the rule X<sub>cur</sub> -> Y<sub>cur</sub> Z<sub>elem</sub>
    return slist;

Note: Some corner cases may not be fixed in above procedure.

Now, for the no. Of rules in GN, note that each variable can get a subscript from 1 to N, and we call the procedure for each rule that a variable heads, so no. Of productions = O(no. Of variables * no. Of productions* N) wrt the old CFG (in CNF).

  • 2
    $\begingroup$ This is very hard to decipher as you are using code instead of a normal description. But if I understand correctly what your algorithm is trying to output, the result is wrong. E.g., if you convert a rule $S\to AB$ to $S_i\to A_iB_j$, there is nothing in the rules that would force $A_i$ to produce a string of length exactly $j-i$. You would need a pair of indices indicating both the starting and ending index, but then the whole grammar has size $\Omega(N^3)$. (I’m pretty sure this, or its variant, is the baseline $O(N^3)$ solution mentioned in the OP.) $\endgroup$ Commented Apr 14 at 7:09
  • $\begingroup$ I thought it would be enough, but if it's not, then i will recheck! $\endgroup$ Commented Apr 14 at 7:23
  • $\begingroup$ Does the algorithm ever take advantage of the fact that $G$ is a deterministic CFG? I'm fairly sure in the case of a general CFG, we would need $O(N^3)$, though I haven't formally proven that. $\endgroup$
    – Jerry Ding
    Commented Apr 18 at 4:26

Your Answer

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

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