Modify DCFG to enforce length limit

Question

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)$.

Answer 1

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).

Answer 2

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, X_i 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):-

subscript(X->YZ,cur){
    if(cur==N){
        if(Y and Z are variables){
            halt();
            return {cur+1};
        }
        // Means it is of the form X->a
        // Add the rule X<sub>cur</sub> -> a
        return {cur+1};
    }
    list={};
    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);
        list.add(new_cur);
    }
    slist={};
    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>
            slist.add(new_cur);
        }
        
    }
    return slist;
}

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

Now, for the no. Of rules in G_N, 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).