The complexity of computing the number of strings of given length in context-free languages

AbstractComputing the number of strings of given length contained in a language is related to classical problems of combinatorics, formal languages and computational complexity. Here we study the complexity of this problem in the case of context-free languages. It is shown that, for unambiguous context-free languages such a computation is “easy” and can be carried out by efficient parallel algorithms. On the contrary, for some context-free languages of ambiguity degree two, the problem becomes intractable. These results are related to other classical subjects concerning counting problems, exponential time recognizable languages and sparse sets