CONTEXT–FREE LANGUAGES OF SUB–EXPONENTIAL GROWTH

MARTIN R. BRIDSON AND ROBERT H. GILMAN

Abstract. There do not exist context-free languages of intermediate growth.

The function γ whose value at each non–negative integer n is the number of words on length n in a fixed formal language L is called the growth function of L. Flajolet [3] asked if there are context–free languages of intermediate growth; that is, such that γ is not bounded above by a polynomial, but lim sup γ(n)/r^{n} = 0 for all r > 1. The answer to this question is a corollary to the following theorem.

Theorem 1. If L is a context–free language with growth function γ, then either there is a number r > 1 and integer n_{0} such that γ(n) ≥ r^{n} for all n ≥ n_{0}, or else L is a bounded language.

A bounded language is one which is a subset of w_{1}^{∗} ⋯ w_{n}^{∗} for some words {w_{1}, …, w_{n}}. Since it is clear that the growth of a bounded language is bounded above by a polynomial, we have the desired corollary.

Corollary 2. There do not exist context–free languages of intermediate growth.

We note that by a recent result of Grigorchuk and Machì there are indexed languages of intermediate growth [4].

Corollary 2 was obtained independently by Roberto Incitti [6]. Theorem 1 occurs in our previous work [1] as a remark that the proof given there of the weaker result [1, Proposition 1.3] suffices for Theorem 1. In this note we give a quicker proof of Theorem 1 based on work of Ginsburg and Spanier [5], who also obtain a corresponding decidability result.

Theorem 3 ([5, Theorem 5.2]). It is decidable whether or not the language L generated by a given context–free grammar is bounded; and if L is bounded, one can effectively find words {w_{1}, …, w_{n}} such that L ⊂ w_{1}^{∗} ⋯ w_{n}^{∗}.

1991 Mathematics Subject Classification. 68Q45.

Key words and phrases. context-free langauges, growth functions.

Bridson’s research is supported by an EPSRC Advanced Fellowship.

Now we prove Theorem 1. Suppose the language L over the finite alphabet Σ is generated by a context–free grammar G with start symbol S. Without loss of generality we may assume that each non–terminal A of G participates in a derivation of some word in L. Write A →^{∗} α to indicate that A derives the sentential form α. Following [5] we define for each non–terminal A

Y_{A} = {u | A →^{∗} uAv for some v ∈ Σ^{∗}}
Z_{A} = {v | A →^{∗} uAv for some w ∈ Σ^{∗}}.

Theorem 4 ([5, Theorem 5.1]). A necessary and sufficient condition that the non–empty language L generated by a context–free grammar G be bounded is that Y_{A} and Z_{A} both be commutative for every non– terminal A of G.

To complete the proof of Theorem 1 it suffices to show that if some Y_{A} or Z_{A} is not commutative, then L_{A}, the language of all words derivable from A, has growth function bounded below by an exponential. Indeed since A occurs in the derivation of at least one word in L, there is a derivation S →^{∗} uAv for some words u, v ∈ Σ^{∗}, and it follows easily that the growth function of L is bounded below by an exponential once the growth function for L_{A} is.

Suppose a particular Y_{A} is not commutative (the argument is similar for Z_{A}) and pick two derivations

A →^{∗} u_{1}Av_{1} A →^{∗} u_{2}Av_{2} u_{1}u_{2} ≠ u_{2}u_{1}.

Choose an integer m with m ≥ |u_{i}|, m ≥ |v_{i}| and m ≥ |w| for some w ∈ L_{A}, and then choose two more integers integers d, e such that u_{1}^{d} and u_{2}^{e} have the same length. Each derivation may be used to expand the non–terminal A occuring in u_{1}Av_{1} and in u_{2}Av_{2}. By iterating these expansions, one sees that for every word W = W (x_{1}, x_{2}) in the free monoid {x_{1}, x_{2}}^{∗}, L_{A} contains W (u_{1}^{d}, u_{2}^{e})wW̄ (v_{1}^{d}, v_{2}^{e}), where W̄ is W written backwards.

If two distinct words W and W′ of the same length k yield the same element of L_{A}, then one of W (u_{1}^{d}, u_{2}^{e}), W′(u_{1}^{d}, u_{2}^{e}) must be a prefix of the other. Because u_{1}^{d} and u_{2}^{e} have the same length, W (u_{1}^{d}, u_{2}^{e}) = W′(u_{1}^{d}, u_{2}^{e}) in this case. As W and W′ are distinct, we must have u_{1}^{d} = u_{2}^{e}. According to [2, Corollary 4.1] or [5, Lemma 5.1], this implies that u_{1} and u_{2} commute. Since u_{1} and u_{2} do not commute, we conclude that the 2^{k} words W of length k yield 2^{k} distinct words W (u_{1}^{d}, u_{2}^{e})wW̄ (v_{1}^{d}, v_{2}^{e}) of length at most (2k + 1)mf in L_{A}. Here f is the maximum of {d, e}.

Hence the growth function γ_{A} of L_{A}, satisfies γ_{A}((2k + 1)mf) ≥ 2^{k} if k ≥ 1.

Suppose n ≥ 6mf. Dividing n by mf we obtain n = (2k + 1)mf + r for some k ≥ 1 and r with 0 ≤ r < 2mf. Thus γ_{A}(n) ≥ 2^{k} and k ≥ (n−3mf)/(2mf) ≥ n/(4mf). Hence n ≥ 6mf implies γ_{A}(n) ≥ r^{n} for r = 2^{−4mf}.

References

[1] M. Bridson and R. Gilman, Formal language theory and the geometry of 3-manifolds, Commentarii Math. Helv., 71, 1996, 525–555.

[2] C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages, vol. 1, G. Rozenberg and A. Salomaa eds., Springer Verlag, 1997, 329–438

[3] P. Flajolet, Analytic models and ambiguity of context–free languages, Theoret. Comput. Sci. 49 (1987), 283–309.

[4] R. I. Grigorchuk and A. Machì, An example of an indexed language of intermediate growth. Theoret. Comput. Sci. 215 (1999), 325–327.

[5] S. Ginsburg and E. Spanier, Bounded ALGOL–like languages, Trans. Amer. Math. Soc. 113 (1964), 333-368.

[6] R. Incitti, The growth of context–free languages, to appear.

Martin R. Bridson, Mathematical Institute, 24–29 St. Giles, Oxford OX1 3LB, UK

  E-mail address: bridson@maths.ox.ac.uk

Robert H. Gilman, Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USA

  E-mail address: rgilman@sitvxc.stevens-tech.edu