OFFSET
1,3
COMMENTS
Let G be an acyclic context-free grammar in Greibach normal form. If we bound the grammar size above by n, then the maximum word length that can be generated by such a grammar G is a(n). Here, grammar size is understood as the sum of the lengths of the right-hand sides in all productions.
Also, for a context-free language L, let mpcf(L) denote the minimum constant such that the context-free pumping lemma holds for L. In Gruber/Holzer (2025b), it is shown that mpcf(L) <= a(n)+1 for each language that can be generated by some context-free grammar in Greibach normal form of size at most n.
As proved in Gruber/Holzer (2025a), the corresponding sequence for unrestricted context-free grammars is A000792, and an analogous statement holds for the pumping constant in that case.
REFERENCES
H. Gruber and M. Holzer, On Pumping Constants and Smallest Grammars for Context-Free Languages. In M. Dolores Jiménez López and György Vaszil, editors, Languages of Cooperation and Communication: Essays Dedicated to Erzsébet Csuhaj-Varjú to Celebrate Her Scientific Career, volume 15840 of Lecture Notes in Computer Science, pages 54--68. Springer, 2025.
H. Gruber and M. Holzer, On Pumping Constants and Smallest Grammars in Greibach Normal Form, preprint, 2025.
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,4,-4).
FORMULA
In Gruber/Holzer (2025b) it is shown that
1. a(n) obeys the recurrence
a(n) = max_{1<=k<=n-2}(k * a(n-k-1)+1) with base values a(1)=a(2)=1.
2. a(n) = 4*a(n-5)+1 for n >=21. (This implies that, for n large enough, the maximum is always attained at k=4.)
3. a(n) = {
n - 1, if 2 <= n <= 6
(31 * 4^((n - 8)/5) - 1) / 3, if n mod 5 = 3 and n >= 8
(40 * 4^((n - 9)/5) - 1) / 3, if n mod 5 = 4 and n >= 9
(52 * 4^((n - 10)/5) - 1) / 3, if n mod 5 = 0 and n >= 10
(94 * 4^((n - 12)/5) - 1) / 3, if n mod 5 = 2 and n >= 12
(283 * 4^((n - 16)/5) - 1) / 3, if n mod 5 = 1 and n >= 16
}
G.f.: -(6*x^20-6*x^19+5*x^16-5*x^15+2*x^12-x^11-x^10+x^8+x^7-2*x^6+3*x^5-x^4-x^3-x^2-1) / ((x-1)*(4*x^5-1)). - Alois P. Heinz, Oct 09 2025
EXAMPLE
An acyclic context-free grammar in Greibach normal form attaining the bound for n=21 has the following productions:
A_1 -> aA_2A_2A_2A_2
A_2 -> aA_3A_3A_3
A_3 -> aA_4A_4A_4
A_4 -> aA_5A_5A_5
A_5 -> aA_6A_6
A_6 -> a
The lengths of the right-hand sides correspond to the fact that
a(21) = 4*a(16)+1, a(16)=3*a(12)+1, a(12)=3*a(8)+1, a(8)=3*a(4)+1, and a(4)=2*a(1)+1.
PROG
(Python) def lambda_values(n_max: int):
"""
Compute lambda(m) for:
lambda(1)=1, lambda(2)=1
for m>=3: lambda(m) = max_{1<=j<=m-2} (1 + j*lambda(m-j-1))
Returns (lambda_list, argmax_list).
"""
lam = [0]*(n_max+1)
argmax_j = [0]*(n_max+1)
lam[1] = 1
if n_max >= 2:
lam[2] = 1
for m in range(3, n_max+1):
best_val = -1
best_j = 0
for j in range(1, m-1): # j = 1..m-2
cand = 1 + j * lam[m-j-1]
if cand > best_val:
best_val = cand
best_j = j
lam[m] = best_val
argmax_j[m] = best_j
return lam, argmax_j
(Python)
def A389642(n):
if n<20: return (1, 1, 2, 3, 4, 5, 7, 10, 13, 17, 22, 31, 41, 53, 69, 94, 125, 165, 213)[n-1]
q, r = divmod(n, 5)
return (((850, 1132, 1504, 1984, 2560)[r]<<(q-4<<1))-1)//3 # Chai Wah Wu, Jan 23 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Hermann Gruber, Oct 09 2025
STATUS
approved
