<p>A partial answer: The number of productions needed by a (not necessarily deterministic) context-free grammar generating <span class="math-container">$L\cap \Sigma^{\le N}$</span> in the worst case is <span class="math-container">$\Theta(N^2)$</span>, as given in Theorem 4 of</p>
<blockquote>
<p>W. Bucher, H.A. Maurer, K. Culik, D. Wotschke, <a href="https://doi.org/10.1016/0304-3975(81)90044-X" rel="nofollow noreferrer">Concise description of finite languages</a>, Theoretical Computer Science 14(3), 1981, pp. 227-246.</p>
</blockquote>
<p>For convenience, we reproduce the construction and the outline of the lower bound. Given a context-free grammar <span class="math-container">$G=(V,\Sigma, P, S)$</span> in Chomsky normal form, for every variable <span class="math-container">$A\in V$</span>, we introduce variables <span class="math-container">$A^{(1)}, \ldots A^{(N)}$</span> and productions</p>
<ul>
<li><span class="math-container">$A^{(i)}\to B^{(i-k)}C^{(k)}$</span>, for <span class="math-container">$i=2$</span> to <span class="math-container">$n$</span> and <span class="math-container">$k=1$</span> to <span class="math-container">$i-1$</span> and all productions of type <span class="math-container">$A\to BC$</span>,</li>
<li><span class="math-container">$S^{(i)}\to S^{(i-1)}$</span>, for <span class="math-container">$i=2$</span> to <span class="math-container">$n$</span></li>
<li><span class="math-container">$A^{(1)}\to a$</span> for all productions of type <span class="math-container">$A\to a$</span> or <span class="math-container">$S \to \varepsilon$</span>.</li>
</ul>
<p>For correctness proof, see the proof in the paper.</p>
<p><s>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).</s></p>
<p>For the lower bound, they prove that the language <span class="math-container">$U_n = \{\,a^k b^k ca^\ell b^\ell d a^mb^m \mid 0 \le k+\ell+m \le n \,\}$</span> requires <span class="math-container">$\Omega(n^2)$</span> context-free productions. As noted in the comments, the language <span class="math-container">$U := \bigcup_n U_n$</span> is a deterministic context-free language, so this gives a quadratic lower bound for the problem asked by the OP.</p>
<p>More precisely, they prove that the language <span class="math-container">$\widehat{U}_n = U_n \cap  \Sigma^n$</span> is <em>incompressible by context-free grammars</em>, 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).</p>
<p>Also, they show that for a finite language <span class="math-container">$L$</span> whose words are of length at most <span class="math-container">$n$</span>, the required number of context-free productions for generating <span class="math-container">$L \cap  \Sigma^n$</span> is a lower bound for the required number of context-free productions for generating <span class="math-container">$L$</span> (Lemma 2.2).</p>

CC BY-SA 4.0
2024-04-23T06:30:34.527Z
Great! The lower bound is a very interesting result, I can see how this $U_n$ language is deterministic too
Jerry Ding
CC BY-SA 4.0
2024-04-23T08:32:54.383Z
Concerning whether the grammar is “deterministic”, first, as discussed in comments on the other question by the OP (https://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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-04-23T08:36:40.877Z
... 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.
Emil Jeřábek
CC BY-SA 4.0
2024-04-23T10:36:30.617Z
@EmilJeřábek thank you, I have to admit that I didn't think too hard about determinism.
Hermann Gruber
CC BY-SA 4.0
2024-04-23T10:39:48.603Z
@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.
Hermann Gruber
CC BY-SA 4.0
2024-04-23T11:05:44.563Z
@EmilJeřábek yes, that was intended. Thank you for also putting this right!
Hermann Gruber
CC BY-SA 4.0
2024-04-21T21:28:53.887Z
2024-04-23T20:05:41.470Z
2024-04-23T20:05:41.470Z
Hermann Gruber
<p>Here is one algorithm:-</p>
<p><strong>Step 1:</strong> Convert the grammar to CNF. This should take time O(square of no. Of productions)</p>
<p><strong>Idea:</strong> The basic idea is to subscript each use of non terminals. For each variable X, X<sub>i</sub> on the head of a rule denotes that the substitution of this rule is to match ith letter in the input word.</p>
<p><strong>Step 2:</strong> For start rule, S-&gt;AB, we shall call subscript(S-&gt;AB,0).</p>
<p>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):-</p>
<pre><code>subscript(X-&gt;YZ,cur){
    if(cur==N){
        if(Y and Z are variables){
            halt();
            return {cur+1};
        }
        // Means it is of the form X-&gt;a
        // Add the rule X&lt;sub&gt;cur&lt;/sub&gt; -&gt; a
        return {cur+1};
    }
    list={};
    for each production of form Y-&gt; WU{
        // W or U can be epsilon or terminal as well, but not together
        new_cur = subscript(Y-&gt;WU,cur);
        list.add(new_cur);
    }
    slist={};
    for each production of form Z-&gt;PQ{
        // P or Q can be epsilon or terminal also, but not together
        for elem in list{
            new_cur = subscript(Z-&gt;PQ,elem);
            // Add the rule X&lt;sub&gt;cur&lt;/sub&gt; -&gt; Y&lt;sub&gt;cur&lt;/sub&gt; Z&lt;sub&gt;elem&lt;/sub&gt;
            slist.add(new_cur);
        }
        
    }
    return slist;
}
</code></pre>
<p>Note: Some corner cases may not be fixed in above procedure.</p>
<p>Now, for the no. Of rules in G<sub>N</sub>, 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).</p>

CC BY-SA 4.0
2024-04-14T07:09:53.040Z
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.)
Emil Jeřábek
CC BY-SA 4.0
2024-04-14T07:23:32.670Z
I thought it would be enough, but if it's not, then i will recheck!
harshchy2210
CC BY-SA 4.0
2024-04-18T04:26:35.120Z
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.
Jerry Ding
CC BY-SA 4.0
2024-04-14T04:02:16.373Z
2024-04-14T04:07:05.373Z
2024-04-14T04:07:05.373Z
harshchy2210
<p>Given a deterministic context-free grammar <span class="math-container">$G$</span> that generates the language <span class="math-container">$L$</span>, is there an efficient algorithm that can be used to construct another DCFG <span class="math-container">$G_N$</span> that generates the language <span class="math-container">$\{ s \in L \mid \lvert s \lvert \leq N \}$</span>? In other words, an algorithm that creates a DCFG whose language is the set of valid strings from <span class="math-container">$L$</span> that are under a certain length <span class="math-container">$N$</span>.</p>
<p>For the algorithm, what would be the size of <span class="math-container">$G_N$</span> in terms of <span class="math-container">$N$</span>? I'm especially interested if there are algorithms that result in <span class="math-container">$G_N$</span> of size <span class="math-container">$O(N)$</span> or even <span class="math-container">$O(N^2)$</span>.</p>
<p>I'm also interested if there are arguments, perhaps heuristic ones, for a lower bound on the size of <span class="math-container">$G_N$</span>. Because DCFG's can be parsed efficiently, I suspect <span class="math-container">$O(N)$</span> is possible, but maybe I'm wrong and adding the length limit forces a worst case of <span class="math-container">$O(N^3)$</span>.</p>

CC BY-SA 4.0
2024-03-14T08:11:38.427Z
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)$?
D.W.
CC BY-SA 4.0
2024-03-14T08:31:31.423Z
@D.W. Great to see you, I see this approach is related to your algorithm [here](https://cs.stackexchange.com/questions/148133), 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.
Jerry Ding
CC BY-SA 4.0
2024-04-17T15:38:29.070Z
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)$.
Hermann Gruber
CC BY-SA 4.0
2024-04-18T04:24:38.277Z
@HermannGruber Yeah, the size of the original $G$ grammar is not dependent on $N$
Jerry Ding
<fl.formal-languages><automata-theory><context-free><grammars>
Modify DCFG to enforce length limit
Jerry Ding
# Modify DCFG to enforce length limit

(Asked by: username_0 on 2024-03-14)

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

**Tags:** fl.formal-languages, automata-theory, context-free, grammars

> **Comments:**
> **username_1**: 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)$?  
> **username_0**: @username_1 Great to see you, I see this approach is related to your algorithm [here](https://cs.stackexchange.com/questions/148133), 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.  
> **username_2**: 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)$.  
> **username_0**: @HermannGruber Yeah, the size of the original $G$ grammar is not dependent on $N$  

---

## 2 answers

### Answer by username_2 on 2024-04-21. Score: 3 | Accepted answer

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](https://doi.org/10.1016/0304-3975(81)90044-X), 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).

> **Comments:**
> **username_0**: Great! The lower bound is a very interesting result, I can see how this $U_n$ language is deterministic too  
> **username_3**: Concerning whether the grammar is “deterministic”, first, as discussed in comments on the other question by the OP (https://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 ...  
> **username_3**: ... 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.  
> **username_2**: @EmilJeřábek thank you, I have to admit that I didn't think too hard about determinism.  
> **username_2**: @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.  
> **username_2**: @EmilJeřábek yes, that was intended. Thank you for also putting this right!  

---

### Answer by username_4 on 2024-04-14. Score: 0

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):-
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 Xcur -> 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 Xcur -> Ycur Zelem
            slist.add(new_cur);
        }
        
    }
    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).

> **Comments:**
> **username_3**: 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.)  
> **username_4**: I thought it would be enough, but if it's not, then i will recheck!  
> **username_0**: 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.  

---

